Advertisement
C3EQUALZ

Алгоритм поиска кратчайшего пути

Nov 24th, 2022 (edited)
688
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 5.77 KB | None | 0 0
  1. ###Поиск в глубину. Используется для нахождения всех путей в графе от заданной точки. В качестве графа должен быть задан словарь. В ином случае функция не будет работать. start - это начальная точка графа, а end - конец, data - наш путь, visited - точки, которые уже посетили. В начале добавлю в data нашу стартовую точку, так как с неё начинаем движение. Рассматриваем соседи нашей точки, исключая уже посещенные. Если нашли подходящего соседа, то добавляем в data и visited, заходим рекурсивно, посещая каждого соседа данной точки. Работает с помощью метода исключения, где мы оставляем только один способ поиска пути.
  2. def dfs(start, end, graph, data, visited):
  3.     if len(data) == 0:
  4.         data.append(start)
  5.         visited.add(start)
  6.  
  7.     if start == end:
  8.         return print(f'Путь - {data}, а количество ребер {len(data) - 1}')
  9.  
  10.     for next in set(graph[start]) - visited:
  11.         data.append(next)
  12.         visited.add(next)
  13.         dfs(next, end, graph, data, visited)
  14.         data.pop()
  15.         visited.remove(next)
  16.  
  17. ###Алгоритм Дейкстры. В качестве графа принимаем словарь, где value тоже словарь, содержащий точки, в которые можем попасть, и вес. Каждое практически действие сопровождается комментарием.
  18. graph = {
  19.     'a': {'b': 5, 'c': 2},
  20.     'b': {'a': 5, 'c': 7, 'd': 8},
  21.     'c': {'a': 2, 'b': 7, 'd': 4, 'e': 8},
  22.     'd': {'b': 8, 'c': 4, 'e': 6, 'f': 4},
  23.     'e': {'c': 8, 'd': 6, 'f': 3},
  24.     'f': {'e': 3, 'd': 4},
  25.     }
  26. start = input('Введите начальную точку ')
  27. end = input('Введите конечную точку ')
  28.  
  29. def dejksra(start, end, graph):
  30.     ### Задаем начальные переменные
  31.     shortest_distances = {i: float('inf') for i in graph} ##самые короткие расстояния до каждой точки
  32.     shortest_distances[start] = 0 #нет расстояния между стартом и стартом
  33.     path = {} #самые короткий путь для каждой точки, здесь именно буква
  34.     travel = [] #наша траектория движения.
  35.     ###
  36.     while len(graph) > 0:
  37.         min_node = None #каждый раз буду заходить в новую точку, поэтому обнуляю
  38.         for current_node in graph: #прохожусь по ключам графу
  39.             if min_node == None:
  40.                 min_node = current_node #в первый раз у нас будет None, а дальше будет наша текущая точка
  41.             elif shortest_distances[min_node] > shortest_distances[current_node]: #сравниваем с каждым элементом по ключу
  42.                 min_node = current_node
  43.         for node, value in graph[min_node].items(): #раскрываем словарь внутри словаря {(b,5),(c,2)]
  44.             if value + shortest_distances[min_node] < shortest_distances[node]: #расстояние от старта до данной точки сравниваем
  45.                 shortest_distances[node] = value + shortest_distances[min_node] #запоминаем самый короткий путь от начала до данной точки
  46.                 path[node] = min_node #запоминаем в словарь самую минимальную точку
  47.         graph.pop(min_node) #удаляем минимальную точку, чтобы в неё не вернуться
  48.     ###Восстановление пути из словаря. Каждый раз так возвращаем.
  49.     while end != start:
  50.         try:
  51.             travel.insert(0, end)  
  52.             end = path[end]
  53.         except:
  54.             print('Невозможно восстановить путь.')
  55.             break
  56.     travel.insert(0, start)
  57.     if shortest_distances[min_node] != float('inf'):
  58.         return print(f'Минимальный путь - {travel}, а самая минимальная сумма - {shortest_distances[min_node]}')
  59.  
  60.  
  61. dejksra(start, end, graph)
  62.  
  63. ###Поиск в ширину. Для удобства можно использовать deque. Создаем словарь, где для каждой точки будет запоминаться путь от старта. Расстояние старта принимаем за 0 (расстояние от 1 до 1 == 0). Текущее число удаляем для поиска соседей с помощью словаря графа. Если мы его не проходили, то от прошлого добавляем 1. Добавляем в очередь для повторной итерации. Делается все, пока не пройдем полностью граф.
  64.  
  65. from collections import deque
  66.  
  67. def bfs(graph, root):
  68.     distances = {}
  69.     distances[root] = 0
  70.     q = deque([root])
  71.     while q:
  72.         current = q.popleft()
  73.         for neighbor in graph[current]:
  74.             if neighbor not in distances:
  75.                 distances[neighbor] = distances[current] + 1
  76.                 q.append(neighbor)
  77.     return distances
  78.  
  79. graph = {1:[2,3], 2:[1,3], 3:[1,2,4], 4:[1]}
  80. root = 1
  81. print(bfs(graph, root))
  82.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement