Как Dijkstra и Bellman-Ford находят кратчайшие пути?

Question

Accepted Answer

Оба находят **кратчайшие пути от источника** в взвешенном графе. **Dijkstra** быстрее, но требует **неотрицательных** весов; **Bellman-Ford** медленнее, но обрабатывает **отрицательные** рёбра и обнаруживает отрицательные циклы.

## Dijkstra (жадный + min-heap)

Повторно расширяй ближайший непосещённый узел и релаксируй его соседей.

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

Релаксируй **все** рёбра V-1 раз; дополнительная релаксация означает отрицательный цикл.

## Почему это важно

| | Dijkstra | Bellman-Ford |
|---|---------|----------------|
| Веса | неотрицательные | любые (включая отрицательные) |
| Время | O((V+E) log V) | O(V·E) |
| Отр. цикл | н/п | обнаруживает |

## Когда использовать / ошибки

Используй **Dijkstra** по умолчанию для неотрицательных весов (карты, сети). Используй **Bellman-Ford**, если существуют отрицательные рёбра (напр. арбитраж). Dijkstra молча ломается на отрицательных весах — классическая ловушка.

## Почему это важно

Алгоритмы кратчайшего пути питают маршрутизацию, навигацию, сетевые протоколы и анализ стоимости зависимостей.

Знание ограничения неотрицательности весов в Dijkstra предотвращает неправильные ответы на практике.

Идея релаксации соединяет жадное и DP мышление, делая это богатой темой на уровне senior.

	Dijkstra	Bellman-Ford
Веса	неотрицательные	любые (включая отрицательные)
Время	O((V+E) log V)	O(V·E)
Отр. цикл	н/п	обнаруживает