V
V
VovanZ2014-05-12 11:19:44
Mathematics
VovanZ, 2014-05-12 11:19:44

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

1 answer(s)
R
Rsa97, 2014-05-12
@Rsa97

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  -

Starting point A (A = 0). We build paths from A (B = 4, C = 1), add them to the queue. We build paths from B (C = 1). We build paths from C (B = 2). And again, we need to rebuild the paths from B, since a shorter path was found to it.
Therefore, Dijkstra uses a sorted queue, then there is no need to re-scan the points.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question