Graph shortest path infinite cycle

Question

So my paint skills are not the best but I think it shows the example well. Imagine I want to calculate the shortest path between A and C, considering all the algorithms I've found are greedy, wouldn't it be stuck in an infinite cycle between A and B?

Any sugestions?

Thanks in advance

Answer 1

No, there shouldn't be an infinite cycle.

Visited and unvisited nodes in the graph are kept track of, and a visited node will never be visited again.

In your example:

1. Mark all nodes as unvisited, except for the starting node which is visited
2. Starting with A, visit B, mark B as visited
3. B can only visit A or C, but A has already been marked as visited
4. The only available node is C, which is unvisited

Answer 2

I usually put into each node the distance and path (list of nodes) from starting point. When I enter a node I compare current distance against existing distance. if the current distance is shorter than existing, I replace the new path with old path.

Another method is to keep a list of distances at each node to every other node. Fill in this list as you leave each node.

Start at A : Set A already visited. Go to B. Then back to A. A is already visited so at B add distance from B To A as 26. Move from B to D. Then back to B. B already visited so at D add distance D to B as 96. Add distance from D to A as 96 + 26 = 112. Move from D to E. Then back to D. D already visited so at E add distance E to D as 21. Add distance from E to B as 21 + 96 = 117. Add distance E to A as 21 + 96 + 26 = 143.