Member Avatar for alexutza_r_m

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.

  • 2 Contributors
  • 3 Replies
  • 109 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by alexutza_r_m

Recommended Answers

All 3 Replies

Member Avatar for $dunk$

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.

Member Avatar for alexutza_r_m

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

Best regards.

Member Avatar for alexutza_r_m

Thank you a lot. Your idea was great. It solved my problem.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.