algorithm - 有向グラフの特定の頂点を通る最短経路

Question

正のエッジ重みを持つ強く接続された有向グラフG（V、E）があり、V0がVに属しているとします。V0を通るノードのすべてのペア間の最短経路を見つけるアルゴリズムを記述します。

インタビューの質問。明らかに、O（VE）を取るベルマンフォード法を使用できます。

ただし、より良い解決策が存在する必要があります。何か助けてください？

Answer 1

Dijkstra のアルゴリズムを使用することもできると思います。これを 1 回実行して、V0 から他のすべての頂点への最短経路を見つけ、次にもう一度すべての頂点から V0 への最短経路を見つけます (これは、逆エッジを持つグラフで通常の Dijkstra を実行するのと同じです)。次に、任意のペア (V1、V2) について、V1 から V0 および V0 から V2 へのパスを連結します。