Finding Shortest Paths of weighted graph using stacks

Question

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.

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.

Answer 1

As with most graph searching algorithms, you have to keep the state of each node during the searching. The state would have following values: white, gray, black with following interpretation:

• white = node has not yet been discovered during the current search, or it is unreachable.
• gray = node that was discovered, but not yet processed by the search algorithm.
• black = reachable nodes in your graph, that the search algorithm has discovered and also processed.

This labeling ensures that you do not search in endless loops.

To get all shortest paths from a node s to another node e:

• mark all nodes nodes as white.
• then as you visit nodes you label them gray and put them on the stack.
• If you processed all neighbours of a node, you label it black.
• To recover all the shortest paths from s to e, you need to maintain an array, call it parents, i.e. parents(v) = u, meaning v was visited from u.

After you searched the whole graph, you proceed backwards from the end node e via the parents array, to get all the shortest paths from the starting node s.