Šie algoritmai randa trumpiausius kelius iš šaltinio svertame grafe. Dijkstra yra greitesnis, bet reikalingi neneigiami svoriai; Bellman-Ford yra lėtesnis, bet gali valdyti neigiamus briaunas ir aptinka neigiamus ciklus.
Nuolat išplečia arčiausią aplankytą mazgą ir susilpnina jo kaimynus.
import heapq
def dijkstra(graph, src):
dist = {n: float('inf') for n in graph}
dist[src] = 0
pq = [(0, src)] # (distance, node)
while pq:
d, u = heapq.heappop(pq) # closest first
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]: # relax edge
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
Susilpnina visas briaunas V-1 kartų; tolimesnis susilpninimas reiškia neigiamą ciklą.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Svoriai | neneigiami | bet kokie (įskaitant neigiamus) |
| Laikas | O((V+E) log V) | O(V·E) |
| Neigiamas ciklas | n/a | aptinka |
Dijkstrą naudokite pagal numatytuosius nustatymus neneigiamų svorių atveju (žemėlapiai, tinklai). Bellman-Ford naudokite, kai egzistuoja neigiamos briaunos (pvz., arbitražas). Dijkstra tyliai sutrinka neigiamų svorių atveju — klasikinis spąstai.
Trumpiausiųjų keliųalgoritmais paremtas maršrutizavimas, navigacija, tinklo protokolai ir priklausomybės sąnaudų analizė.
Žinojimas apie Dijkstros neneigiamų svorių apribojimą apsaugo nuo klaidingų atsakymų praktikoje.
Susilpninimo idėja sujungia greediš ir DP mąstymą, todėl tai yra turtinga aukšto lygio tema.