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

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

Новые блоги и статьи Все статьи Все блоги /
Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .
1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip

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

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

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

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

@Catstail Супер-модератор 38193 / 21126 / 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 Супер-модератор 38193 / 21126 / 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

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

Решение