Kuinka Dijkstra ja Bellman-Ford löytävät lyhimmät polut?

Question

Accepted Answer

Molemmat löytävät **lyhimmät polut lähteestä** painotetusta verkkograafista. **Dijkstra** on nopeampi mutta vaatii **ei-negatiivisia** painoja; **Bellman-Ford** on hitaampi mutta käsittelee **negatiivisia** kaaria ja havaitsee negatiiviset syklit.

## Dijkstra (greedy + min-heap)

Laajenna toistuvasti lähintä käymätöntä solmua ja relaksoi sen naapureita.

```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 (DP-style relaxation)

Relaksoi **kaikki** kaaret V-1 kertaa; lisärelaksaatio tarkoittaa negatiivista sykliä.

## Vertailu

| | Dijkstra | Bellman-Ford |
|---|---------||
| Painot | ei-negatiivisia | mikä tahansa (sisältäen negatiiviset) |
| Aika | O((V+E) log V) | O(V·E) |
| Neg. sykli | ei käytettävissä | havaitsee sen |

## Milloin käyttää / Sudenkuopat

Käytä **Dijkstraa** oletuksena ei-negatiivisille painoille (kartat, verkot). Käytä **Bellman-Fordia**, kun negatiivisia kaaria on olemassa (esim. arbitraasi). Dijkstra epäonnistuu hiljaa negatiivisilla painoilla — klassinen sudenkuoppa.

## Miksi se on tärkeää

Lyhimpien polkujen algoritmit ohjaavat reititysta, navigointia, verkkoprotokolleja ja riippuvuuskustannusten analyysia.

Ei-negatiivisen painon rajoituksen tunteminen Dijkstrassa estää vääriä vastauksia käytännössä.

Relaksaation ajatus yhdistää ahne- ja DP-ajattelun, mikä tekee siitä rikkaan senior-tason aiheen.