ორივე პოულობენ უმოკლეს გზებს წყაროდან წონიანი გრაფიკში. Dijkstra უფრო სწრაფია მაგრამ მოითხოვს არა-უარყოფითი წონებს; Bellman-Ford უფრო ნელია მაგრამ справляется უარყოფითი კიდეებით და აღმოაჩენს უარყოფითი ციკლებს.
მეორდებით აფართოვებს უახლოეს ეწვეული კვანძს და ამსუბუქებს მის მეზობლებს.
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
დამსუბუქებს ყველა კიდეს V-1 ჯერ; შემდგომი დამსუბუქება ნიშნავს უარყოფით ციკლს.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| წონები | არა-უარყოფითი | ნებისმიერი (უარყოფიტის ჩათვლით) |
| დრო | O((V+E) log V) | O(V·E) |
| უარყ. ციკლი | არა | აღმოაჩენს |
გამოიყენეთ Dijkstra ნაგულისხმევად არა-უარყოფითი წონებისთვის (რუკები, ქსელები). გამოიყენეთ Bellman-Ford როდესაც უარყოფითი კიდეები არსებობს (მაგ. არბიტრაჟი). Dijkstra მწყვილად შეწყვეტს უარყოფით წონებზე — კლასიკური ხარვეზი.
უმოკლესი გზის ალგორითმები მართავენ მარშრუტიზაციას, ნავიგაციას, ქსელის პროტოკოლებს და დამოკიდებულების ხარჯის ანალიზს.
Dijkstra-ს არა-უარყოფითი წონის შეზღუდვის ცოდნა ხელს უშლის არასწორი პასუხებს ფიელდში.
დამსუბუქების ধারণა აერთიანებს욕심 და DP აზრს, რაც საამაო უმცროსი დონის თემა გახდის.