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.

Replies

  • durga ch
    durga ch
    start 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
    Rishabh1234
    durga
    start 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
    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.
  • rahul69
    rahul69
    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.
    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.
    😀
  • Rishabh1234
    Rishabh1234
    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.
    😀
    can you please elaborate . i am unable to understand which node you are referring and how you are proposing to split it.
  • durga ch
    durga ch
    if 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
    Rishabh1234
    durga
    if 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
    This will still won't solve the time constraint problem 😔

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...