Dukansu suna samun hanyoyin gida daga tushe a cikin jigon ƙarfi. Dijkstra sannu amma yana buƙatar ƙarfuffuka marasa rashin ; Bellman-Ford sannu amma yana daukar ƙarfuffukan rashin kuma yana gano ƙunkunan rashin.
Fada'ido jigon da ke kushe da samun bakin hausawa.
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
Sankararsa duk ƙarfuffu V-1 kara; sauran sakarda yana nufin ƙunkuni rashin.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Karfuffu | marasa rashin | duk (hakomin rashin) |
| Loka | O((V+E) log V) | O(V·E) |
| Ƙunkuni rashin | n/a | yana gano |
Yi amfani da Dijkstra na mara lallai don karfuffukan marasa rashin (taswira, shabakan). Yi amfani da Bellman-Ford ina da rashin ƙarfuffu (m.s, arbitrage). Dijkstra sannu ne a kan karfuffukan rashin — sako na klassiko.
Mawajen gida algorithms na bugi jadawa, senarwa, miyakkatun yarukan sadarwa, da binciken farashin cuci.
Sanin takaitacciyar ƙarfuffu marasa rashin akan Dijkstra yana hare wa karya masu karya a filin.
Ji na sakarka yana jijiya sauran ta greedy da DP, yana sauran hada-hadi mai yawa na jirgin senior.