CODEWITHSUNDEEP
data-structuresgraph
Abhishek Gahlout
Abhishek Gahlout

Reputation: 3462

Which algorithm is best to traverse weighted , directed graph provided the start and end point?

Hi I am looking for the best algorithm to find out the optimal path traversing a directed and weighted graph.

[Hi all, I am editing the problem for explaining my requirement completely]

e.g: If in a graph of 5 nodes (let's assign number 1,2,3,4,5 to all the 5 nodes respectively), if I wish to start traversing from node 2 and end up at 4 , covering all the nodes, then which is the best algorithm to solve the problem ?

We can have two assumptions :

a) There is always an edge between any two nodes. (means for two nodes (A and B) there is an edge from A to B and from B to A as well.

b) we can traverse a node twice (If necessary to traverse complete graph).

Upvotes: 4

Views: 8121

Answers (2)

Sebastian
Sebastian

Reputation: 8005

Using Dijkstra is the way to go, but you can tweak the algorithm (which by default is a single source - multiple sink algorithm) to be a single-source single-sink implementation.

Basically instead of starting with one node (the source node) start with both the start and end nodes at the same time. For the sink nodes traverse the edges in reverse direction. You can use two priority queues and for each step peak which queue to remove the next entry from. Whenever you are trying to enqueue a new element, check whether it is already contained in the other queue. In this case you have found a path from the source to the sink.

Upvotes: 2

Konrad Rudolph
Konrad Rudolph

Reputation: 545648

This is a classical problem in computer science with a well-known solution.

Do the graphs have non-negative edge weights only? Then use Dijkstra’s algorithm or A*. Otherwise use the Bellman–Ford algorithm. If you want to find all pairs of shortest paths between all nodes, use the algorithm of Floyd & Warshall.

Upvotes: 6

Related Questions