How to traverse a directed weighted graph with one obligatory weighted stop, however there are multiple stops, and multiple exits

Question

Given a directed adjacency matrix, find the shortest weight path to an exit, however, you must first stop at one of potentially multiple (up to the number of vertices) weighted stops, where each stop can be weighted differently. You only need to stop at one of these stops, which have their locations and weights listed, and can then go to any of the given exits. The required complexity should be O(Edges*log(Verticies))

I am struggling to implement Dijkstra's Algorithm using a min-heap and priority queue, as I am unsure how to evaluate between different stops. I am given a list of the potential stops, and their weights, as well as the locations of all of the exits, and a starting vertex. What would be the steps to figuring out an optimal and efficient solution?

Answer 1

• Construct S a path with 'infinite' length
• Use Dijkstra to find P1 a vector of cheapest paths from start to each obligatory stop
• LOOP O over obligatory stops
  • Use Dijkstra to find P2 a vector of cheapest paths from O to each exit
  • SELECT so the cheapest path from start to O ( from P1 )
  • LOOP p2 over P2
    • IF length so + length p2 < length S
      • Set S = length so + length p2
• OUTPUT S