graph-algorithm - 特定のエッジを通過する最短経路アルゴリズム

Question

「通過する必要がある」とマークされた少なくとも1つのエッジを通過するグラフ内の最短経路を見つける必要があります。何か案は？これを達成するために、ダイクストラのアルゴリズムを変更できますか？

Answer 1

Cを通過する必要があるAからBへのパスについて、1つはAからCへ、もう1つはCからBへの2つの最短パスとして計算します。