Dijkstra法は負の重み辺が含まれるグラフでも常に正しく動作するか？

Dijkstra法は「未確定の最短距離の中で最小のものを確定する」という貪欲戦略を取り、これは全辺の重みが非負であることを前提に正当性が保証されます。負の重みがあると、確定したはずの頂点に後からより短い経路が現れる可能性があり、誤った結果を返すためBellman-Ford法など負辺を扱えるアルゴリズムを使う必要があります。