Dijkstra's algorithm for finding a path in a tree with loops
Who can tell you how the Dijkstra algorithm should work correctly when traversing a tree with cycles. I.e. there is a tree that reflects a maze, it has cycles, you need to find the shortest path from one arbitrary vertex to another. You cannot convert a tree to an adjacency matrix. For example, the tree looks like in the picture. It turns out that the weights of all edges are equal to 1. How should the algorithm behave correctly when it determines the cell label starting from the one highlighted in green, should it it should be marked as visited after the edges of its neighbors are relaxed, if so, then the algorithm will not end after it moves from the green vertex to the yellow one, since all its neighbors will be marked as visited. Perhaps I am asking a very confused question, if that correct. Thank you! z. s. I write the code in java if there are examples.
2 answers
A little confusion in terms of graph theory. There is no "tree with cycles", because by definition, a tree is a connected acyclic (that is, without cycles) graph.
Dijkstra, even on a tree, even on a graph, will work the same way. The main condition is that the weights of all arcs (or edges in the case of no orientation) are non-negative, greater than or equal to zero. The implementation of Dijkstra in Java can be viewed here http://cybern.ru/algoritm-dejkstry-realizaciya-na-java.html
In this case, if the weights of all edges are equal to 1, then the shortest path from one arbitrary vertex to another can be found by the usual search in width. It will even be asymptotically faster by an order of magnitude, since the Deisktra works for the square of the number of vertices in a tree or graph, and the search is wide by O (N).
You can read about breadth-first search here: http://cybern.ru/obxod-v-shirinu.html
At the end of the article there are links by implementing a breadth-first crawl in Java, C++ , and Python
As far as I understand, Dijkstra's algorithm is applicable to a graph with cycles if there are no cycles in the graph of the negative weight (i.e., the negative total length).
On the other hand, if there is a negative weight cycle in the graph (located on the path from the source to the target vertex), the task of finding the minimum path does not make sense, since the weight of the path leading through the cycle can be made as small as you like by "twisting" the circles around the cycle.
Situations like you have in the picture, when running the algorithm, it will not happen. If the algorithm first selects the white three as the vertex with the minimum weight, it will put a four, and mark the white three as visited. Then it will select the yellow triple as the minimum unvisited element, and write it to the green vertex 4.