https://en.wikipedia.org/wiki/Shortest_path_problem
Napiszmy funkcję wyznaczającą śieżkę pomiędzy dwoma wierzchołkami w grafie. Argumenty funkcji to graf, wierzchołki początkowy i końcowy. Funkcja zwraca listę różnych wierzchołków (bez cykli) łącznie z początkowym i końcowym. Jeżeli funkcja nie może znaleźć ścieżki, wtedy zwraca None. Algorytm wykorzystuje technikę algorytmów z powrotami (backtracking): sprawdza każdą możliwość, aż znajdzie rozwiązanie.
def find_path(graph, start, end, path=[]):
path = path + [start] # powstaje nowa lista!
if start == end:
return path
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath:
return newpath
return None
Stosunkowo łatwo możemy zmienić funkcję tak, aby zwracała listę wszystkich ścieżek bez cykli pomiędzy dwoma wierzchołkami.
def find_all_paths(graph, start, end, path=[]):
path = path + [start] # powstaje nowa lista!
if start == end:
return [path]
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
Inny wariant funkcji daje najkrótszą ścieżkę pomiędzy wierzchołkami (najkrótszą w sensie liczby krawędzi należących do ścieżki).
def find_shortest_path(graph, start, end, path=[]):
path = path + [start] # powstaje nowa lista!
if start == end:
return path
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
W grafach ważonych długość ścieżki jest rozumiana jako suma wag (długości) krawędzi. Cormen dodatkowo przyjmuje, że grafy są skierowane, co pozwala na istnienie różnych wag w zależności od kierunku przechodzenia od wierzchołka do wierzchołka. Rozważa się dwa rodzaje problemów.