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

@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!).

Новые блоги и статьи Все статьи Все блоги /
Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip
Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере нетипового документа выдачи шин для спецтехники с табличной частью, разработанного в конфигурации КА2. Данные берутся из. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git

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

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

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

@Catstail Супер-модератор 38194 / 21127 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 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 Супер-модератор 38194 / 21127 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 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 Супер-модератор 38194 / 21127 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 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 Супер-модератор 38194 / 21127 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	18.11.2021, 16:21
	TangerineLeaf, 100! это огромное число. Надо искать оптимальный алгоритм... 0

@Catstail Супер-модератор 38194 / 21127 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 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 Супер-модератор 38194 / 21127 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 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

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

Решение