search

Kumar-laxmi / Algorithms

A Repository for algorithms in C, C++, Python and Java
Apache License 2.0
311 stars 364 forks source link

Multistage Graph (Shortest Path) #1196

Closed tarunvyshnav777 closed 1 year ago

tarunvyshnav777 commented 1 year ago

Feature = Shortest Distance in Multistage Graph

A Multistage graph is a directed, weighted graph in which the nodes can be divided into a set of stages such that all edges are from a stage to next stage only (In other words there is no edge between vertices of same stage and from a vertex of current stage to previous stage).

The goal of multistage graph problem is to find minimum cost path from source to destination vertex. image

Dijkstra’s Algorithm of Single Source shortest paths will find shortest paths from source to all other nodes which is not required in this case. So it will take a lot of time and it doesn’t even use the SPECIAL feature that this MULTI-STAGE graph has.

Approach: The best option is Dynamic Programming. So we need to find Optimal Sub-structure, Recursive Equations and Overlapping Sub-problems.

Attribute: To be added in C, C++, Java and Python. Added comments to explain the flow and logic of code to the reader. I would like to work on this issue. Can you assign it to me under SSOC '23?

Kumar-laxmi commented 1 year ago

Assigned! @tarunvyshnav777 : C, C++, Python and Java