Faigheann an bheirt na bealaí is gearr ó fhoinse i ngraf ualaithe. Tá Dijkstra níos tapa ach riachtanach ualáideanna neamh-dhiúltach ; tá Bellman-Ford níos moille ach cuireann sé le fréamhaircanna dhiúltacha agus braitheann sé timthriallai dhiúltacha.
Leathnú arís agus arís eile an nód neamhthabhaithe is gaire agus a chomharsana a scaoileadh.
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
Scaoil gach fréamharc V-1 uair; scaoileadh breise a chiallaíonn timthriall dhiúltach.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Ualáideanna | neamh-dhiúltach | ar bith (incl. diúltach) |
| Am | O((V+E) log V) | O(V·E) |
| Timthriall diúltach | n/a | braitheann sé |
Úsáid Dijkstra go réamhshocraithe do ualáideanna neamh-dhiúltacha (léarscáileanna, líonraí). Úsáid Bellman-Ford nuair a bhíonn fréamhaircanna dhiúltacha ann (m.sh., arbitrage). Brisidh Dijkstra i ngan fhios ar ualáideanna dhiúltacha — gaistí clasaiceach.
Cumhachtaíonn algoritimí bealaigh is gearr an driuch, an nascleanúint, na prótacail líonra, agus anailís chostas eisimirce.
Aithint a bhaint as an srian ualaithe neamh-dhiúltach ar Dijkstra a bhreachaitheadh i réimse na fréamhaircí.
Na hoibríochta scaoilte a nascadh greedy agus DP a thuiscint, é a dhéanamh mar ábhar saibhir do leibhéal sinsir.