Si e gjejnë Dijkstra dhe Bellman-Ford rrugën më të shkurtër?

Question

Accepted Answer

Të dyja gjejnë **rrugët më të shkurtra nga një burim** në një graf të ponderuar. **Dijkstra** është më e shpejtë, por kërkon pesha **jo-negative**; **Bellman-Ford** është më e ngadaltë, por përballon skajet **negative** dhe zbulon cikle negative.

## Dijkstra (greedy + min-heap)

Zgjerojë në mënyrë të përsëritur nyjen më të afërt të pa-vizituar dhe relakson fqinjëtë e saj.

```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 (relaksim në stil DP)

Relaksoni **të gjitha** skajet V-1 herë; relaksim i mëtejshëm do të thotë një cikel negativ.

## Krahasimi

| | Dijkstra | Bellman-Ford |
|---|---------|--------------||
| Peshat | jo-negative | të çdo lloji (përfshirë negative) |
| Koha | O((V+E) log V) | O(V·E) |
| Cikel negativ | n/a | e zbulon atë |

## Kur të përdorni / kurthë

Përdorni **Dijkstra** me parazgjedhje për peshat jo-negative (harta, rrjete). Përdorni **Bellman-Ford** kur ekzistojnë skajet negative (p.sh., arbitrazh). Dijkstra dështon në heshtje në peshat negative — një kurth klasik.

## Pse është e rëndësishme

Algoritmët e rrugës më të shkurtër fuqizojnë rrugëzimin, navigimin, protokollet e rrjetit dhe analizën e kostos të varësisë.

Dija e kufizimit të peshës jo-negative në Dijkstra parandalon përgjigje të gabuara në praktikë.

Ideja e relaksimit lidh mendimin greedy dhe DP, duke e bërë atë një temë të pasur në nivel të lartë.