Answer the question
In order to leave comments, you need to log in
How to write an algorithm for finding the shortest distance?
Given a directed directed graph, you need to find the distance to all vertices from a given one.
It is clear that such a problem is solved by Dijkstra's algorithm.
However, what if this algorithm is easier to implement? What if we add the vertices for which we found the best path not to the priority queue, but to the regular queue (FIFO)?
I understand that such an algorithm will not be optimal.
The question is: will it be correct? If not, please provide a counterexample.
Answer the question
In order to leave comments, you need to log in
Then you will have to re-examine the vertices if a shorter path has been found for them.
Example:
. A B C
A - 4 1
B 4 - 1
C 1 1 -
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question