Hi, everybody!

I am new to this forum.

I have a problem with an oriented weighted graph, more precisely, I have to find the shortest path between 2 nodes, but this path should pass through a given intermediary node. For example, I have a graph with 5 nodes, namely A, B, C, D, E. I have to find the shortest path from A to E, but this path should involve node C as well. With the weights the graph has, the shortest path should be, for example, A-B-D-E.

I used Dijkstra's algorithm to find the shortest path from A to E, that is the path A-B-D-E. That worked out fine. But I have no idea how I could change the code to accept the node that I am interested in, that is node C.

If you have any ideas, I would be very grateful to you.

Thanks a lot.

8 Years
Discussion Span
Last Post by alexutza_r_m

It seems to me that you need to break the search into 2 separate operations. For example, if you start at A and want to end up at E, going through C then you would calculate the shortest path from A to C, then calculate the shortest path from C to E.


Hi. Thank you a lot for the reply. I will use your idea and I will tell you the results.

Best regards.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.