Search code examples
graph-algorithmshortest-pathdijkstraedges

Shortest path algorithm that passes through certain edges


I need to find the shortest path in a graph that passes through at least one edge marked as "must pass". Any ideas? Could Dijkstra's algorithm be modified in order to achieve this?


Solution

  • For the path from A to B that must pass through C, compute it as two shortest paths, one from A to C, and another from C to B.