Hvordan finder Dijkstra og Bellman-Ford korteste veje?

Question

Accepted Answer

Begge finder **korteste veje fra en kilde** i en vægtet graf. **Dijkstra** er hurtigere men kræver **ikke-negative** vægte; **Bellman-Ford** er langsommere men håndterer **negative** kanter og opdager negative cykler.

## Dijkstra (greedy + min-heap)

Gentagende udvid den nærmeste ubesøgte knude og slak af dens naboer.

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

Slak af **alle** kanter V-1 gange; yderligere slakhed betyder en negativ cykel.

## Sammenligning

| | Dijkstra | Bellman-Ford |
|---|---------||
| Vægte | ikke-negative | enhver (inkl. negative) |
| Tid | O((V+E) log V) | O(V·E) |
| Neg. cykel | n/a | registrerer den |

## Hvornår skal det bruges / faldgruber

Brug **Dijkstra** som standard for ikke-negative vægte (kort, netværk). Brug **Bellman-Ford** når negative kanter findes (f.eks. arbitrage). Dijkstra bryder stiltiende på negative vægte — en klassisk fælde.

## Hvorfor det betyder noget

Korteste-vej-algoritmer driver rutekørsel, navigation, netværksprotokoller og afhængighedsomkostningsanalyse.

At kende begrænsningen for ikke-negative vægte på Dijkstra forhindrer forkerte svar i praksis.

Slakheds-ideen forbinder grådigt og DP-tænkning, hvilket gør det til et rigt emne på seniorplan.