CrazyEngineers
  • 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
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies
  • durga ch

    MemberApr 22, 2015

    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
    Are you sure? This action cannot be undone.
    Cancel
  • Rishabh1234

    MemberApr 22, 2015

    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.
    Are you sure? This action cannot be undone.
    Cancel
  • rahul69

    MemberApr 23, 2015

    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.
    😀
    Are you sure? This action cannot be undone.
    Cancel
  • Rishabh1234

    MemberApr 23, 2015

    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.
    Are you sure? This action cannot be undone.
    Cancel
  • durga ch

    MemberApr 23, 2015

    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
    Are you sure? This action cannot be undone.
    Cancel
  • Rishabh1234

    MemberApr 24, 2015

    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 😔
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register