Найти оптимальный путь по графу

@alilxxey · Регистрация: 09.12.2020

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

Здравствуйте! Всегда относился с неким страхом к рекурсивным функциям, мне они не очень понятны. Теперь нужно написать программу, которая ищет оптимальный путь по "графу" из точки a в точку b. Я так понимаю, это можно решить классическим перебором, более того - я даже смогу решить это обычным перебором, но требуется решить это именно рекурсией. Задача такова: задан граф(пример графа в прикрепленном изображении), дана начальная и конечная точки, даны цены перехода из одной точки в другую, т.е. '1 2 7' - перейти из точки 1 в точку 2 стоит 7. И тд. Решить требуется рекурсией. Я не прошу присылать готовый код, тем более что я не указал четких условий, прошу навести меня на мысль. Спасибо

@anton78spb · 17.10.2021, 01:33

alilxxey, Вроде это называется алгоритм Дейкстры. Там есть что-то типа поиск в глубину и поиск в ширину.

@Exp2dot7 · 17.10.2021, 09:09

граф не ориентированный, составить матрицу 6*6 и в ребрах допустим 5-6(4-5,5-4=9),
у кого ребер нет(5-2,5-1,5-5 и пр.=0)вот по этой матрице рекурсивно DFS

@Catstail · 17.10.2021, 14:38

Exp2dot7, лучше BFS...

Добавлено через 25 секунд
anton78spb, и алгоритм Форда-Беллмана подойдет.

@alilxxey · 17.10.2021, 15:22 **[ТС]**

переписал алгоритм Дейкстры, слегка адаптировав его под свою задачу

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
def way(n, s, matrix):
    valid = [True] * n
    weight = [1000000] * n
    weight[s] = 0
    for i in range(n):
        min_weight = 1000001
        d = -1
        for j in range(n):
            if valid[j] and weight[j] < min_weight:
                min_weight = weight[j]
                d = j
        for z in range(n):
            if weight[d] + matrix[d][z] < weight[z]:
                weight[z] = weight[d] + matrix[d][z]
        valid[d] = False
    return weight
 
'''
a = []
while k := list(map(int, input().split())):
    a.append(k)
start, end = tuple(a.pop(-1))
#print(way(a, start))
v = set()
for i in a:
    for ii in i[:-1]:
        v.add(ii)
'''
a = [[1000000, 10, 1000000, 1000000, 1000000],
     [10, 1000000, 1, 1000000, 6],
     [1000000, 1, 1000000, 1, 1000000],
     [1000000, 1000000, 1, 1000000, 2],
     [1000000, 6, 1000000, 2, 1000000]]
print(way(5, 0, a))

не понимаю как с ним работать, я очень сильно запутался. n - кол-во вершин, s - номер стартовой вершины, matrix - матрица соответствия. Возвращает список весов перехода от начальной до последней вершине графа. Работает корректно только при s=0.
* 1000000 - несуществующая грань

@no swear · 17.10.2021, 19:06

anton78spb, Здравствуйте! Алгоритм Дейкстры предполагает использования динамического программирования с жадным перебором вершин.
alilxxey, Добрый вечер! Если вам чётка указали на то что нужно решить рекурсией то скорее всего не предполагается использовать какие либо алгоритмы на графах, а просто путём перебора выбрать оптимальный путь от точки A до точки B. Перебор осуществлять, как ответил Exp2dot7,, через DFS.

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

Исходя из этого под описания рекурсивного поиска попадает только алгоритм DFS.

Catstail, Здравствуйте! BFS тут вряд ли подойдёт, потому что рёбра имеют вес.

@Catstail · 17.10.2021, 19:39

no swear, да, я неправ. Нужен DFS. Вот честный перебор всех каркасов с поиском кратчайшего пути. Этот алгоритм гораздо менее эффективен, чем чем алгоритм Дейскстры. Но он удовлетворяет условиям задачи:

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
graph={(1,3):9, (1,2):7, (1,6):14, (2,4):15, (3,4):11, (3,6):2, (4,5):6, (5,6):9}
 
# Дать список всех вершин, связанных с текущей
# и непосещенных
 
def get_bound(g,v,path):
    r=[]
    for pair,_ in g.items():
        if (v in pair):
            if v==pair[0]:
                q=pair[1]
            else:
                q=pair[0]
            if not (q in path):
                r.append(q)
    return r            
 
# Генерация всех каркасов графа,  
# начинающихся в cтартовой вершине (тут рекурсия!)
 
def all_paths(graph,start,pth,stk,res):
    bounds=get_bound(graph,start,pth)
    if len(bounds)>0:
        for v in bounds:
            all_paths(graph,v,[v,start]+pth,[v]+stk,res)
    else:
        if len(stk)==0:
            res.append(pth[-1::-1])
        else:
            all_paths(graph,stk[0],pth,stk[1:],res)
    return res    
 
# Поиск пути в финишную вершину
 
def search_path(tree,fin):
    q=fin
    res=[]
    while True:
        k=tree.index(q)
        p=tree[k-1]
        res=[(p,q)]+res
        if k==1:
            return res
        q=p
 
# Получить длину пути 
 
def length_path(graph,pth):
    s=0
    for pair in pth:
        rpair=(pair[1],pair[0])
        s+=graph.get(pair,0)+graph.get(rpair,0)
    return s    
 
# Парадная программа
 
def task(graph,start,fin):
    
    all_pth=all_paths(graph,start,[],[start],[])
 
    shortest_path=search_path(all_pth[0],fin)
    shortest_len =length_path(graph,shortest_path)
    
    for pth in all_pth[1:]:
        
        path=search_path(pth,fin)
        length=length_path(graph,path)
        
        if length<shortest_len:
            shortest_len=length
            shortest_path=path
 
    return shortest_path,shortest_len        
 
print(task(graph,6,4))

@alilxxey · 17.10.2021, 21:23 **[ТС]**

Catstail, хорошее решение. но граф

Кликните здесь для просмотра всего текста

1 2 1
2 3 2
3 4 3

зацикливает.
из 2 в 4.

@no swear · 17.10.2021, 23:30

alilxxey, Надо сохранять все полученные пути(вершины) от старта до финиша и затем каждый раз когда будете доходит до финиша, нужно будет проверить полученный путь(вершины) со всеми предыдущими путями(вершинами).

Добавлено через 12 минут
И ещё вместе с этим надо будет постоянно обновлять список использованных вершин при каждом заходе или выходе из рекурсии.

К примеру, начали путь в вершине 1 и хотим попасть в вершину 5. Из 1ой вершины идём во вторую и помечаем 1ю как использованную used[1] = true, из второй в 3ю и помечаем 2ю как использованную used[2] = true, из 3й в 4ю и used[3] = true, из 4й в 5ю used[5] = true.

Теперь на выходе из рекурсии на 5ой вершине used[5] = false, переходим в 4ю вершину, из 4й некуда идти потому что used[2] = true, переход в третью вершину и used[4] = false. Идём из 3й в 6ю и used[3] = true так и остаётся, из 6й в 5ю и used[6] = true.

Выходим из 5й в 6ю, из 6й некуда идти потому что used[1] = true

@Catstail · 18.10.2021, 10:41

no swear, это не совсем так. Проблема не в поиске каркасов, а в построении пути. Чуть позже выложу исправленный вариант.

Добавлено через 1 час 25 минут
Вот исправленный вариант. На самом деле, это вариант бэктрекинга (перебора с возвратом). Он генерирует все стягивающие деревья (каркасы) графа, начиная со стартовой вершины. Потом, перебирая каркасы, ищет путь до финишной вершины с кратчайшим весом.

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
80
81
82
83
#graph={(1,3):9, (1,2):7, (1,6):14, (2,4):15, (3,4):11, (3,6):2, (4,5):6, (5,6):9}
graph={(1,2):1, (2,3):2, (3,4):3}
 
# Дать список всех вершин, связанных с текущей
# и непосещенных
 
def get_bound(g,v,path):
    r=[]
    for pair,_ in g.items():
        if (v in pair):
            if v==pair[0]:
                q=pair[1]
            else:
                q=pair[0]
            if not (q in path):
                r.append(q)
    return r            
 
# Генерация всех каркасов графа,  
# начинающихся в cтартовой вершине
 
def all_paths(graph,start,pth,stk,res):
    
    bounds=get_bound(graph,start,pth)
    
    if len(bounds)>0:
        for v in bounds:
            all_paths(graph,v,[v,start]+pth,[v]+stk,res)
    else:
        if len(stk)==0:
            res.append(pth[-1::-1])
        else:
            all_paths(graph,stk[0],pth,stk[1:],res)
    return res    
 
# Поиск пути в финишную вершину
 
def search_path(tree,start,fin):
 
    q=fin
    res=[]
 
    while True:
        k=tree.index(q)
        p=tree[k-1]
 
        res=[(p,q)]+res
 
        if p==start:
            return res
        
        q=p
 
# Получить длину пути 
 
def length_path(graph,pth):
    s=0
    for pair in pth:
        rpair=(pair[1],pair[0])
        s+=graph.get(pair,0)+graph.get(rpair,0)
    return s    
 
# Парадная программа
 
def task(graph,start,fin):
    
    all_pth=all_paths(graph,start,[],[start],[])
 
    shortest_path=search_path(all_pth[0],start,fin)
    shortest_len =length_path(graph,shortest_path)
    
    for pth in all_pth[1:]:
        
        path=search_path(pth,start,fin)
        length=length_path(graph,path)
        
        if length<shortest_len:
            shortest_len=length
            shortest_path=path
 
    return shortest_path,shortest_len        
 
print(task(graph,2,4))

Добавлено через 1 минуту
alilxxey, поправил решение.

@alilxxey · 18.10.2021, 11:06 **[ТС]**

Catstail, отличное решение, спасибо большое! Буду разбираться.

@Catstail · 03.05.2022, 09:12

Если нужно задавать граф в диалоге. Как вариант:

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#graph={(1,3):9, (1,2):7, (1,6):14, (2,4):15, (3,4):11, (3,6):2, (4,5):6, (5,6):9}
#graph={(1,2):1, (2,3):2, (3,4):3}
 
# Дать список всех вершин, связанных с текущей
# и непосещенных
 
def get_bound(g,v,path):
    r=[]
    for pair,_ in g.items():
        if (v in pair):
            if v==pair[0]:
                q=pair[1]
            else:
                q=pair[0]
            if not (q in path):
                r.append(q)
    return r            
 
# Генерация всех каркасов графа,  
# начинающихся в cтартовой вершине
 
def all_paths(graph,start,pth,stk,res):
    
    bounds=get_bound(graph,start,pth)
    
    if len(bounds)>0:
        for v in bounds:
            all_paths(graph,v,[v,start]+pth,[v]+stk,res)
    else:
        if len(stk)==0:
            res.append(pth[-1::-1])
        else:
            all_paths(graph,stk[0],pth,stk[1:],res)
    return res    
 
# Поиск пути в финишную вершину
 
def search_path(tree,start,fin):
 
    q=fin
    res=[]
 
    while True:
        k=tree.index(q)
        p=tree[k-1]
 
        res=[(p,q)]+res
 
        if p==start:
            return res
        
        q=p
 
# Получить длину пути 
 
def length_path(graph,pth):
    s=0
    for pair in pth:
        rpair=(pair[1],pair[0])
        s+=graph.get(pair,0)+graph.get(rpair,0)
    return s    
 
# Парадная программа
 
def task(graph,start,fin):
    
    all_pth=all_paths(graph,start,[],[start],[])
 
    shortest_path=search_path(all_pth[0],start,fin)
    shortest_len =length_path(graph,shortest_path)
    
    for pth in all_pth[1:]:
        
        path=search_path(pth,start,fin)
        length=length_path(graph,path)
        
        if length<shortest_len:
            shortest_len=length
            shortest_path=path
 
    return shortest_path,shortest_len        
 
# Ввод графа
 
def get_graph():
    g={}
    print("Вводите ребра графа. Ввод нулевой вершины - конец.")
    while True:
        a=int(input("Нач. вершина="))
        if a==0:
            break
        b=int(input("Кон. вершина="))
        if b==0:
            break
        l=int(input("Длина ребра="))
        g[(a,b)]=l
    print("Граф задан.")
    start=int(input("Стартовая вершина пути="))
    finish=int(input("Финишная вершина вершина пути="))
    return (start,finish,g)    
 
# Стартовая процедура
 
def start():
    (s,f,g)=get_graph()
    print(task(g,s,f))
    
start()

Новые блоги и статьи Все статьи Все блоги /
Переходник 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	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

@alilxxey 712 / 351 / 120 Регистрация: 09.12.2020 Сообщений: 918

	Найти оптимальный путь по графу 17.10.2021, 00:42. Показов 12216. Ответов 11 Метки кратчайший путь, обходы графа (Все метки) Здравствуйте! Всегда относился с неким страхом к рекурсивным функциям, мне они не очень понятны. Теперь нужно написать программу, которая ищет оптимальный путь по "графу" из точки a в точку b. Я так понимаю, это можно решить классическим перебором, более того - я даже смогу решить это обычным перебором, но требуется решить это именно рекурсией. Задача такова: задан граф(пример графа в прикрепленном изображении), дана начальная и конечная точки, даны цены перехода из одной точки в другую, т.е. '1 2 7' - перейти из точки 1 в точку 2 стоит 7. И тд. Решить требуется рекурсией. Я не прошу присылать готовый код, тем более что я не указал четких условий, прошу навести меня на мысль. Спасибо Миниатюры 0

@anton78spb 1956 / 874 / 352 Регистрация: 05.09.2021 Сообщений: 1,387
	17.10.2021, 01:33
	alilxxey, Вроде это называется алгоритм Дейкстры. Там есть что-то типа поиск в глубину и поиск в ширину. 3

@Exp2dot7 Заблокирован
	17.10.2021, 09:09
	граф не ориентированный, составить матрицу 6*6 и в ребрах допустим 5-6(4-5,5-4=9), у кого ребер нет(5-2,5-1,5-5 и пр.=0)вот по этой матрице рекурсивно DFS 2

@Catstail Супер-модератор 38192 / 21125 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	17.10.2021, 14:38
	Exp2dot7, лучше BFS... Добавлено через 25 секунд anton78spb, и алгоритм Форда-Беллмана подойдет. 2

@no swear 192 / 166 / 82 Регистрация: 01.07.2016 Сообщений: 943
	17.10.2021, 19:06
	anton78spb, Здравствуйте! Алгоритм Дейкстры предполагает использования динамического программирования с жадным перебором вершин. alilxxey, Добрый вечер! Если вам чётка указали на то что нужно решить рекурсией то скорее всего не предполагается использовать какие либо алгоритмы на графах, а просто путём перебора выбрать оптимальный путь от точки A до точки B. Перебор осуществлять, как ответил Exp2dot7,, через DFS. Я даже скажу больше, я уверен что не надо использовать готовые алгоритмы на графах по типу Дейкстры и прочих. Потому как эти алгоритмы не являются рекурсивными Исходя из этого под описания рекурсивного поиска попадает только алгоритм DFS. Catstail, Здравствуйте! BFS тут вряд ли подойдёт, потому что рёбра имеют вес. 2

@alilxxey 712 / 351 / 120 Регистрация: 09.12.2020 Сообщений: 918
	17.10.2021, 21:23 [ТС]
	Catstail, хорошее решение. но граф Кликните здесь для просмотра всего текста 1 2 1 2 3 2 3 4 3 зацикливает. из 2 в 4. 1

@no swear 192 / 166 / 82 Регистрация: 01.07.2016 Сообщений: 943
	17.10.2021, 23:30
	alilxxey, Надо сохранять все полученные пути(вершины) от старта до финиша и затем каждый раз когда будете доходит до финиша, нужно будет проверить полученный путь(вершины) со всеми предыдущими путями(вершинами). Добавлено через 12 минут И ещё вместе с этим надо будет постоянно обновлять список использованных вершин при каждом заходе или выходе из рекурсии. К примеру, начали путь в вершине 1 и хотим попасть в вершину 5. Из 1ой вершины идём во вторую и помечаем 1ю как использованную used[1] = true, из второй в 3ю и помечаем 2ю как использованную used[2] = true, из 3й в 4ю и used[3] = true, из 4й в 5ю used[5] = true. Теперь на выходе из рекурсии на 5ой вершине used[5] = false, переходим в 4ю вершину, из 4й некуда идти потому что used[2] = true, переход в третью вершину и used[4] = false. Идём из 3й в 6ю и used[3] = true так и остаётся, из 6й в 5ю и used[6] = true. Выходим из 5й в 6ю, из 6й некуда идти потому что used[1] = true 0

@alilxxey 712 / 351 / 120 Регистрация: 09.12.2020 Сообщений: 918
	18.10.2021, 11:06 [ТС]
	Catstail, отличное решение, спасибо большое! Буду разбираться. 1

Найти оптимальный путь по графу

Решение