Кратчайший путь по графу

@TangerineLeaf · Регистрация: 17.11.2021

Студворк — интернет-сервис помощи студентам

Есть граф, все вершины соединены между собой, известны расстояния между каждой парой вершин. Также известна начальная вершина и конечная.

Нужно перейти от начальной до конечной вершины, посетив все остальные, при этом пройтись по кратчайшему пути. Помогите, пжлст, подобрать нужный алгоритм. А ещё лучше написать код с этим алгоритмом на Python, либо словесно детально описать его.

@Catstail · 17.11.2021, 13:32

Сообщение от TangerineLeaf

все вершины соединены между собой

- как это? Каждая с каждой? Что-то не нравится мне эта формулировка. Дай точную формулировку, как в задании.

@TangerineLeaf · 17.11.2021, 13:36 **[ТС]**

Там не совсем граф. Координатная плоскость, даны координаты всех точек + координаты начальной и конечной, нужно пройти из начала в конец через все точки. Для проекта нужно, сформулированного задания нет. Расстояния между точками я могу найти и занести в матрицу, а что с этим всем дальше делать не понимаю.

@Catstail · 17.11.2021, 14:12

Можно попытаться идти из начальной точки каждый раз в ближайшую непосещенную...

@TangerineLeaf · 17.11.2021, 20:19 **[ТС]**

Это не всегда кратчайший путь, приведу пример: Начало 71;36, конец 8;18. Нужно посетить точки 12:45 и 79;90.
Если посещать ближайшие, то выйдет путь начало (71;36) > 12;45 > 79;90 > конец (8;18)
А кратчайший путь будет путь начало (71;36) > 79;90 > 12;45 > конец (8;18)

Потому и ищу алгоритм для нахождения кратчайшего пути :/

@Catstail · 17.11.2021, 22:28

TangerineLeaf, странно считаете: расстояние (71,36)-(12,45)=59.7, а расстояние (71,36)-(79,90)=54.6 ...

@TangerineLeaf · 17.11.2021, 22:46 **[ТС]**

Ошибочка вышла... Тогда за место 79, 90 возьмём 100,100

Как мне кажется, ближайший путь нужно искать исходя из того, что сначала нужно посетить все точки за начальной (отдаляясь от начальной и от конечной, причём до начальной расстояние меньше, чем до конечной). После пройтись по всем точкам между начальной и конечной. А далее пройтись по всем точкам за конечной и прийти в конечную. Но я не знаю по какому принципу посещать эти три группы точек так, чтобы в итоге получился кратчайший путь.
Может быть всё-таки есть какой-нибудь подходящий алгоритм для графов?)

@Catstail · 18.11.2021, 09:59

Здесь действительно полный граф. Каждая вершина соединена с каждой. Искать кратчайший путь из A в Б можно алгоритмом Форда-Беллмана или Дейкстры. Но эти алгоритмы ищут кратчайший путь, который не обязан включать все вершины. Боюсь, что здесь - только прямой перебор (а это O(n!)). Cколько точек, кстати?

@TangerineLeaf · 18.11.2021, 15:52 **[ТС]**

Нет точного кол-ва, думаю, не более 100, а скорее и нескольких десятков хватит.

@Catstail · 18.11.2021, 16:21

TangerineLeaf, 100! это огромное число. Надо искать оптимальный алгоритм...

@TangerineLeaf · 18.11.2021, 17:19 **[ТС]**

Ну, значит обойдусь парой десятков. У меня нет внешних ограничений, делаю скорее для себя.
Пытаюсь решить перебором так, как умею, но ничего не выходит.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import math
from array import *
 
 
# Матрица
def matr(lis):
    matr = []
    lis_id = []
    lis_idN = []
    for i in range(len(lis)):
        mat = []
        for k in range(i):
            mat.append(matr[k][i])
        x, y = map(int, lis[i].split())
        x_rast = max(x, xk) - min(x, xk)
        y_rast = max(y, yk) - min(y, yk)
        rast = math.sqrt(x_rast ** 2 + y_rast ** 2)
        lis_id.append(rast)
        x_rast = max(x, x0) - min(x, x0)
        y_rast = max(y, y0) - min(y, y0)
        rast = math.sqrt(x_rast ** 2 + y_rast ** 2)
        lis_idN.append(rast)
        for j in range(i, len(lis)):
            if i == j:
                mat.append(0)
                continue
            xs, ys = map(int, lis[j].split())
            x_rast = max(xs, x) - min(xs, x)
            y_rast = max(ys, y) - min(ys, y)
            rast = math.sqrt(x_rast ** 2 + y_rast ** 2)
            mat.append(rast)
        matr.append(mat)
    return matr, lis_id, lis_idN
 
# Поиск кратчайшего пути
# pro - пройденные точки, mn - минимальный путь, put - текущий путь, id - текущая точка, pro_mn - последовательность посещения точек при минимально пути, li
def funk(pro, mn, put, id, pro_mn):
    pro.append(id) #добавляем в список пройденных точек
    if len(pro) == len(matriza):
        put += lis_id[id] # Если прошли все точки, то добавляем расстояние от последней до финиша
        if put < mn or mn == -1: # Если путь меньше, то меняем мин значения
            mn = put
            pro_mn = pro
    else:
        for i in range(len(matriza)):
            if i in pro: #Если i точку уже прошли, то пропускаем её
                continue
            put += matriza[id][i] # Прибавляем расстояние от текущей до следующей
            id = i # "Переходим" в след точку
            put_new, pro_new = funk(pro, mn, put, id, pro_mn) #Уходим в след функцию и принимаем оттуда найденные мин значения пути и посещённых точек
            if put_new < mn or mn == -1:
                mn = put_new
                pro_mn = pro_new
    return mn, pro_mn
 
#Забираем входные данные
x0, y0 = map(int, input().split()) #Начальная точка
xk, yk = map(int, input().split()) #Конечная точка
n = int(input()) # Кол-во точек
graf = []
for i in range(n):
    x, y = map(int, input().split())
    graf.append(str(x) + " " + str(y))
 
matriza, lis_id, lis_idN = matr(graf) # matriza - расстояния между точками (не считая точек старта и финиша), lis_id - расстояния между точка финиша и любой другой точкой, lis_idN - расстояния между точкой старта и любой другой точкой
 
mn = -1
pro = []
put = 0
pro_mn = []
for i in range(len(matriza)):
    id = i
    put = lis_idN[i] # Изначально добавляем расстояние от старта до i точки
    put_new, pro_new = funk(pro, mn, put, id, pro_mn)
    if put_new < mn or mn == -1:
        mn = put_new
        pro_mn = pro_new
 
print(pro_mn)

При
71 36
8 18
2
12 45
100 100

выдаёт 0, 1, 1 Почему-то хочет одну из точек посетить два раза..

Добавлено через 1 минуту
Да и вообще там ответ должен быть 1 0

Добавлено через 3 минуты
Добавив между 73 и 74 строкой pro = [], кажется.. Заработало верно

Добавлено через 38 секунд
Не знаю, правда, как насчёт производительности всего этого безобразия

Добавлено через 11 минут
Всё равно неверно работает(
94 58
30 0
3
56 13
41 48
41 45
Выдаёт 0,1,2, но как минимум один путь меньше есть: 120

Добавлено через 22 минуты
Там из-за вложенности функций значение переменных меняется сразу везде((

@Catstail · 19.11.2021, 09:19

Для двадцати точек придется перебрать 2432902008176640000 комбинаций. Если в лоб.

@TangerineLeaf · 19.11.2021, 13:06 **[ТС]**

А по времени примерно сколько? И как всё-таки реализовать?

@Catstail · 19.11.2021, 19:18

Сообщение от TangerineLeaf

А по времени примерно сколько?

- думаю, много.

Добавлено через 1 минуту
Я бы посоветовал сначала воспользоваться жадным алгоритмом. Потом попытаться улучшить результат.

@TangerineLeaf · 20.11.2021, 23:55 **[ТС]**

Всё пытаюсь решить прямым перебором, но возникла проблема. Решаю рекурсией, при переходе из функции в функцию с глобальным pro_mn творится что-то непонятное, он меняется вместе с локальным pro, как исправить? Не пойму, что с ним не так.
(def funk) Нужно сохранять pro_mn

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import math
from array import *
 
 
# Матрица
def matr(lis):
    matr = []
    lis_id = []
    lis_idN = []
    for i in range(len(lis)):
        mat = []
        for k in range(i):
            mat.append(matr[k][i])
        x, y = map(int, lis[i].split())
        x_rast = max(x, xk) - min(x, xk)
        y_rast = max(y, yk) - min(y, yk)
        rast = math.sqrt(x_rast ** 2 + y_rast ** 2)
        lis_id.append(rast)
        x_rast = max(x, x0) - min(x, x0)
        y_rast = max(y, y0) - min(y, y0)
        rast = math.sqrt(x_rast ** 2 + y_rast ** 2)
        lis_idN.append(rast)
        for j in range(i, len(lis)):
            if i == j:
                mat.append(0)
                continue
            xs, ys = map(int, lis[j].split())
            x_rast = max(xs, x) - min(xs, x)
            y_rast = max(ys, y) - min(ys, y)
            rast = math.sqrt(x_rast ** 2 + y_rast ** 2)
            mat.append(rast)
        matr.append(mat)
    return matr, lis_id, lis_idN
 
def funk(pro, put, id):
    global mn
    global pro_mn
    global count
    global flag
    pro.append(id)
    if len(pro) == len(matriza):
        put += lis_id[id]
        if put < mn or mn == -1:
            mn = put
            pro_mn = pro
    else:
        for i in range(len(matriza)):
            if i in pro:
                continue
            put += matriza[id][i]
            id = i
            funk(pro, put, id)
    pro.pop()
    return
 
 
mn = -1
pro_mn = []
#Забираем входные данные
x0, y0 = map(int, input().split()) #Начальная точка
xk, yk = map(int, input().split()) #Конечная точка
n = int(input()) # Кол-во точек
graf = []
for i in range(n):
    x, y = map(int, input().split())
    graf.append(str(x) + " " + str(y))
 
matriza, lis_id, lis_idN = matr(graf) # matriza - расстояния между точками (не считая точек старта и финиша), lis_id - расстояния между точка финиша и любой другой точкой, lis_idN - расстояния между точкой старта и любой другой точкой
 
for i in range(len(matriza)):
    id = i
    put = lis_idN[i] # Изначально добавляем расстояние от старта до i точки
    pro = []
    funk(pro, put, id)
 
print(pro_mn)

Добавлено через 36 минут
Более актуальный код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import math
from array import *
 
 
# Матрица
def matr(lis):
    matr = []
    lis_id = []
    lis_idN = []
    for i in range(len(lis)):
        mat = []
        for k in range(i):
            mat.append(matr[k][i])
        x, y = map(int, lis[i].split())
        x_rast = max(x, xk) - min(x, xk)
        y_rast = max(y, yk) - min(y, yk)
        rast = math.sqrt(x_rast ** 2 + y_rast ** 2)
        lis_id.append(rast)
        x_rast = max(x, x0) - min(x, x0)
        y_rast = max(y, y0) - min(y, y0)
        rast = math.sqrt(x_rast ** 2 + y_rast ** 2)
        lis_idN.append(rast)
        for j in range(i, len(lis)):
            if i == j:
                mat.append(0)
                continue
            xs, ys = map(int, lis[j].split())
            x_rast = max(xs, x) - min(xs, x)
            y_rast = max(ys, y) - min(ys, y)
            rast = math.sqrt(x_rast ** 2 + y_rast ** 2)
            mat.append(rast)
        matr.append(mat)
    return matr, lis_id, lis_idN
 
def funk(pro, put, id):
    global mn
    global pro_mn
    global count
    global flag
    pro.append(id)
    if len(pro) == len(matriza):
        put += lis_id[id]
        if put < mn or mn == -1:
            mn = put
            pro_mn = pro
        put -= lis_id[id]
    else:
        for i in range(len(matriza)):
            if i in pro:
                continue
            put_x = put
            put_x += matriza[id][i]
            id_x = i
            funk(pro, put_x, id_x)
    pro.pop()
    return
 
 
mn = -1
pro_mn = []
#Забираем входные данные
x0, y0 = map(int, input().split()) #Начальная точка
xk, yk = map(int, input().split()) #Конечная точка
n = int(input()) # Кол-во точек
graf = []
for i in range(n):
    x, y = map(int, input().split())
    graf.append(str(x) + " " + str(y))
 
matriza, lis_id, lis_idN = matr(graf) # matriza - расстояния между точками (не считая точек старта и финиша), lis_id - расстояния между точка финиша и любой другой точкой, lis_idN - расстояния между точкой старта и любой другой точкой
 
for i in range(len(matriza)):
    id = i
    put = lis_idN[i] # Изначально добавляем расстояние от старта до i точки
    pro = []
    funk(pro, put, id)
 
print(pro_mn, mn)

@anton78spb · 21.11.2021, 00:45

TangerineLeaf, Судя по описанию, ваша задача называется "задачей коммивояжёра". Можете погуглить, есть различные варианты ее решения. На сколько я помню, однозначно точное решение у этой задачи есть, только методом перебора, но оно крайне неэффективно по времени. Но есть и эффективные методы, которые дают результат с приемлемой точностью.

@Catstail · 21.11.2021, 07:52

anton78spb, Да это задача коммивояжера по полному графу. Поэтому бэктрекинг здесь выродится в полный перебор. О чем я и писал

@anton78spb · 21.11.2021, 10:11

Catstail, Именно так. И сложность полного перебора там вроде O(n!).

Новые блоги и статьи Все статьи Все блоги /
Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .

@TangerineLeaf 0 / 0 / 0 Регистрация: 17.11.2021 Сообщений: 9

	Кратчайший путь по графу 17.11.2021, 12:29. Показов 6873. Ответов 17 Метки алгоритм, граф (Все метки) Есть граф, все вершины соединены между собой, известны расстояния между каждой парой вершин. Также известна начальная вершина и конечная. Нужно перейти от начальной до конечной вершины, посетив все остальные, при этом пройтись по кратчайшему пути. Помогите, пжлст, подобрать нужный алгоритм. А ещё лучше написать код с этим алгоритмом на Python, либо словесно детально описать его. 0

@TangerineLeaf 0 / 0 / 0 Регистрация: 17.11.2021 Сообщений: 9
	17.11.2021, 13:36 [ТС]
	Там не совсем граф. Координатная плоскость, даны координаты всех точек + координаты начальной и конечной, нужно пройти из начала в конец через все точки. Для проекта нужно, сформулированного задания нет. Расстояния между точками я могу найти и занести в матрицу, а что с этим всем дальше делать не понимаю. 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	17.11.2021, 14:12
	Можно попытаться идти из начальной точки каждый раз в ближайшую непосещенную... 0

@TangerineLeaf 0 / 0 / 0 Регистрация: 17.11.2021 Сообщений: 9
	17.11.2021, 20:19 [ТС]
	Это не всегда кратчайший путь, приведу пример: Начало 71;36, конец 8;18. Нужно посетить точки 12:45 и 79;90. Если посещать ближайшие, то выйдет путь начало (71;36) > 12;45 > 79;90 > конец (8;18) А кратчайший путь будет путь начало (71;36) > 79;90 > 12;45 > конец (8;18) Потому и ищу алгоритм для нахождения кратчайшего пути :/ 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	17.11.2021, 22:28
	TangerineLeaf, странно считаете: расстояние (71,36)-(12,45)=59.7, а расстояние (71,36)-(79,90)=54.6 ... 0

@TangerineLeaf 0 / 0 / 0 Регистрация: 17.11.2021 Сообщений: 9
	17.11.2021, 22:46 [ТС]
	Ошибочка вышла... Тогда за место 79, 90 возьмём 100,100 Как мне кажется, ближайший путь нужно искать исходя из того, что сначала нужно посетить все точки за начальной (отдаляясь от начальной и от конечной, причём до начальной расстояние меньше, чем до конечной). После пройтись по всем точкам между начальной и конечной. А далее пройтись по всем точкам за конечной и прийти в конечную. Но я не знаю по какому принципу посещать эти три группы точек так, чтобы в итоге получился кратчайший путь. Может быть всё-таки есть какой-нибудь подходящий алгоритм для графов?) 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	18.11.2021, 09:59
	Здесь действительно полный граф. Каждая вершина соединена с каждой. Искать кратчайший путь из A в Б можно алгоритмом Форда-Беллмана или Дейкстры. Но эти алгоритмы ищут кратчайший путь, который не обязан включать все вершины. Боюсь, что здесь - только прямой перебор (а это O(n!)). Cколько точек, кстати? 0

@TangerineLeaf 0 / 0 / 0 Регистрация: 17.11.2021 Сообщений: 9
	18.11.2021, 15:52 [ТС]
	Нет точного кол-ва, думаю, не более 100, а скорее и нескольких десятков хватит. 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	18.11.2021, 16:21
	TangerineLeaf, 100! это огромное число. Надо искать оптимальный алгоритм... 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	19.11.2021, 09:19
	Для двадцати точек придется перебрать 2432902008176640000 комбинаций. Если в лоб. 0

@TangerineLeaf 0 / 0 / 0 Регистрация: 17.11.2021 Сообщений: 9
	19.11.2021, 13:06 [ТС]
	А по времени примерно сколько? И как всё-таки реализовать? 0

@anton78spb 1956 / 874 / 352 Регистрация: 05.09.2021 Сообщений: 1,387
	21.11.2021, 00:45
	TangerineLeaf, Судя по описанию, ваша задача называется "задачей коммивояжёра". Можете погуглить, есть различные варианты ее решения. На сколько я помню, однозначно точное решение у этой задачи есть, только методом перебора, но оно крайне неэффективно по времени. Но есть и эффективные методы, которые дают результат с приемлемой точностью. 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	21.11.2021, 07:52
	Сообщение было отмечено TangerineLeaf как решение Решение anton78spb, Да это задача коммивояжера по полному графу. Поэтому бэктрекинг здесь выродится в полный перебор. О чем я и писал 1

@anton78spb 1956 / 874 / 352 Регистрация: 05.09.2021 Сообщений: 1,387
	21.11.2021, 10:11
	Catstail, Именно так. И сложность полного перебора там вроде O(n!). 0

Кратчайший путь по графу

Решение