Dijkstra na Bellman-Ford hupatanaje njia fupi zaidi?

Question

Accepted Answer

Zote mbili hupata **njia fupi zaidi kutoka chanzo** katika grafu yenye uzani. **Dijkstra** ni haraka zaidi lakini inahitaji uzani **wa tidak-negatif**; **Bellman-Ford** ni polepole zaidi lakini inakabili kingo **za tidak-negatif** na kugunza mizunguko ya tidak-negatif.

## Dijkstra (greedy + min-heap)

Inaeneza kwa kurudia nodi iliyokaribika zaidi ambayo haijatembelewa na kurelaksi majibu yake.

```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 (urelaksaji wa mtindo wa DP)

Relaksi **kingo zote** mara V-1; urelaksaji zaidi unamaanisha mizunguko ya tidak-negatif.

## Kulinganisha

| | Dijkstra | Bellman-Ford |
|---|---------|--------------||
| Uzani | wa tidak-negatif | yoyote (kwa ujumla wa tidak-negatif) |
| Wakati | O((V+E) log V) | O(V·E) |
| Mizunguko ya tidak-negatif | n/a | inagunza |

## Wakati wa kutumia / mitego

Tumia **Dijkstra** kwa kawaida kwa uzani wa tidak-negatif (ramani, mitandao). Tumia **Bellman-Ford** wakati kingo za tidak-negatif zipo (mfano, arbitrage). Dijkstra inaona bila sauti kwa uzani wa tidak-negatif — mtego wa kawaida.

## Kwa nini ina umuhimu

Algoritmu za njia fupi zaidi zinaendesha uongezaji, urambazaji, itifaki za mtandao, na uchambuzi wa gharama ya tegemezi.

Ufahamu wa kizuizi cha uzani wa tidak-negatif juu ya Dijkstra kunaepusha majibu mabaya katika sehemu halisi.

Karamu ya urelaksaji inachanganya fikira za greedy na DP, ikiwa ni mada tajika ya kiwango cha juu.