Hur hittar Dijkstra och Bellman-Ford kortaste vägar?

Question

Accepted Answer

Båda hittar **kortaste vägar från en källa** i en viktad graf. **Dijkstra** är snabbare men kräver **icke-negativa** vikter; **Bellman-Ford** är långsammare men hanterar **negativa** kanter och detekterar negativa cykler.

## Dijkstra (girig + min-heap)

Upprepar gång på gång den närmaste besökta noden och relaxerar dess grannar.

```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-liknande relaxering)

Relaxera **alla** kanter V-1 gånger; ytterligare relaxering indikerar en negativ cykel.

## Jämförelse

| | Dijkstra | Bellman-Ford |
|---|---------|--------------||
| Vikter | icke-negativa | valfri (inkl. negativ) |
| Tid | O((V+E) log V) | O(V·E) |
| Neg. cykel | n/a | detekterar den |

## När ska man använda / fallgropar

Använd **Dijkstra** som standard för icke-negativa vikter (kartor, nätverk). Använd **Bellman-Ford** när negativa kanter finns (t.ex. arbitrage). Dijkstra bryter tyst på negativa vikter — en klassisk fälla.

## Varför det spelar roll

Kortaste väg-algoritmer driver routning, navigation, nätverksprotokoll och beroendeanalys.

Kunskap om begränsningen för icke-negativa vikter på Dijkstra förhindrar felaktiga svar i praktiken.

Relaxeringsidén kopplar ihop girig och DP-tänkande, vilket gör det till ett rikt avsnitt på högre nivå.