CODEWITHSUNDEEP
c++algorithmgraphshortest-path
user2878007
user2878007

Reputation: 419

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall algorithm it is kinda of possible, but unfortunately I'm only allowed to use stacks (instead of matrices). I also looked for Dijkstra's algorithm but I could not get the relationship with my problem.picture

Clearly my aim is to get all shortest paths from one point to another one. As I mentioned I will just output the solution from my stack in a vector string. I guess I have to visit each node and what I am most afraid is of getting stacked in a loop or even loosing the track during the search. Also note that this is not a directed graph. If Dijkstra's algorithm is applicable here I would be very grateful if anyone of you would guide me and I would really appreciate any help, suggestion, idea or even a vision for not getting stacked in a loop or loosing the track while searching.

Thanks in advance.

Upvotes: 2

Views: 1601

Answers (1)

artur grzesiak
artur grzesiak

Reputation: 20348

If you just want to have values of all shortest paths from some chosen node to all other nodes you will be fine with Dijkstra algorithm -- it is basically augmented BFS. Once you get the idea behind BFS you should not have any problems with understanding Dijkstra. Actually it is much easier to implement BFS with a single queue than with arrays. Is it some formal (school?) requirement that you have to use stacks. If so it is rather strange... But you can still emulate -- in totally inefficient way -- a queue with two stacks.

(btw. DFS uses stack)

If you want to have all all shortest paths from all nodes to all other nodes, you can just run Dijkstra from each node or you can try Bellman-Ford which is bit faster, but a little bit harder to grasp.

If you want just a shortest path from a single node to some other node, (bit augmented) bidirectional BFS will be the best choice.

If you have Silverlight plugin, you can try this little application in 50% written by me: http://grzesiaka.home.pl/GraphTutor/ you will find there a presentation step-by-step of algorithms you are interested in (with data structures and pseudo-code). Hopefully it helps you!

Upvotes: 1

Related Questions