Kako Dijkstrin in Bellman-Fordov algoritem najdeta najkrajše poti?

Question

Accepted Answer

Oba poiščeta **najkrajše poti iz vira** v utežnem grafu. **Dijkstrin** je hitrejši, vendar potrebuje **nenegativne** uteži; **Bellman-Fordov** je počasnejši, vendar obravnava **negativne** robove in zazna negativne cikle.

## Dijkstrin (požrešen + min-heap)

Neprekinjeno razširja najbližje neobiskane vozlišče in sprostlja njegova sosednja vozlišča.

```python
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
```

## Bellman-Ford (sprostitev v stilu DP)

Sprostitev **vseh** robov V-1 krat; nadaljnja sprostitev pomeni negativen cikel.

## Primerjava

| | Dijkstrin | Bellman-Ford |
|---|---------|--------------||
| Uteži | nenegativne | kateri koli (vključno negativne) |
| Čas | O((V+E) log V) | O(V·E) |
| Neg. cikel | n/a | zazna ga |

## Kdaj uporabiti / pasti

Uporabite **Dijkstrin** privzeto za nenegativne uteži (zemljevidi, omrežja). Uporabite **Bellman-Fordov**, kadar obstajajo negativni robovi (npr. arbitraža). Dijkstrin tiho spodleti pri negativnih utežeh — klasična past.

## Zakaj je to pomembno

Algoritmi za iskanje najkrajše poti poganjajo usmerjanje, navigacijo, protokole omrežij in analizo stroškov odvisnosti.

Znanje omejitve nenegativne uteži pri Dijkstrinu preprečuje napačne odgovore v praksi.

Ideja sprostitve povezuje požrešno in DP razmišljanje, kar jo naredi bogat višje-nivojski predmet.