Finding shortest path for multi-weighted edges between any two nodes
How can we use use Dijkstra's algorithm to find shortest path when there are multiple edges having different weights to go from one node to another and also the availability of edges to go from one mode to another depends on the edge you have taken to come to that path.
This is the situation in the case of trip planning for cheapest path when there are multiple trains/flights between any two stations and arrival time at any intermediate node should be atleast some hours before the departure time of next flight/train.
This is the situation in the case of trip planning for cheapest path when there are multiple trains/flights between any two stations and arrival time at any intermediate node should be atleast some hours before the departure time of next flight/train.
Replies
-
durga chstart with breadth first algorithm. let the distance of all nodes from source node be infinity. as and when a new node gets discovered update the distance with the shorted distance
In case a node has already been discovered, compare the distances and re-update with shortest distance. maintain a DataStructure for path and update the same -
Rishabh1234
This is precisely Dijkstra's algorithm but the case is not that simple.There are more than one edges between any two node and also availability of edge for lets say node 2 to node 3 depends on the edge you have chosen to come to node 2.durgastart with breadth first algorithm. let the distance of all nodes from source node be infinity. as and when a new node gets discovered update the distance with the shorted distance
In case a node has already been discovered, compare the distances and re-update with shortest distance. maintain a DataStructure for path and update the same -
rahul69
Well if that is the case, you can treat that node as two separate nodes. Thus it essentially boils down to simple structure which you can solve using dijkstra algorithm.Rishabh1234This is precisely Dijkstra's algorithm but the case is not that simple.There are more than one edges between any two node and also availability of edge for lets say node 2 to node 3 depends on the edge you have chosen to come to node 2.
😀 -
Rishabh1234
can you please elaborate . i am unable to understand which node you are referring and how you are proposing to split it.rahul69Well if that is the case, you can treat that node as two separate nodes. Thus it essentially boils down to simple structure which you can solve using dijkstra algorithm.
😀 -
durga chif I got it right what Rahul suggested is this
if there are 2 edges a ,b between nodes n1 and n2, then assume n2 as two nodes n2a and n2b , thus you end up having
n1-(a)- n2a and n1-(b)-n2b
also,. I supposed you should first eliminate duplicate edges before computing the end to end shortest path, you can look up the internet to find suitable methods to detect duplicate edges -
Rishabh1234
This will still won't solve the time constraint problem 😔durgaif I got it right what Rahul suggested is this
if there are 2 edges a ,b between nodes n1 and n2, then assume n2 as two nodes n2a and n2b , thus you end up having
n1-(a)- n2a and n1-(b)-n2b
also,. I supposed you should first eliminate duplicate edges before computing the end to end shortest path, you can look up the internet to find suitable methods to detect duplicate edges
You are reading an archived discussion.
Related Posts
I am jobless ECE engineer. What is future scope of automation and embedded systems?what is current and future market trends in those fields? I Wanted to do training course in...
HELLO EVERYBODY, MAY ANYBODY PROVIDE ME ANY PROPER LINKS OR MATERIALS
TO HAVE SOME IDEAS TO WORK ON SQL OTHER THAN THOSE OF DAILY CLASSES OF THE COLLEGE.. ..
I want to search the record from database .I am gonna ask for to date and from date . I want that records between the dates which i am gonna...
WhatsApp voice calling feature is now available to all the iPhone users. The app update version 2.12.1 introduces the much awaited WhatsApp Calling feature on iOS to let you make...
Gionee is back with a new smartphone called 'Gionee Pioneer P4S' in the popular budget range with Rs. 7,779 as its price tag. Ever since Gionee has started to expand...