0
$\begingroup$

I guess this is an implementation question, but I suppose it can be answered for the typical way this algorithm works.

So, most ways the algorithm has been explained to me involve going from a source vertex to another vertex so on and so forth. Will any edges going back to the source vertex or any already visited vertex actually get looked at, or does the algorithm ignore those because they already have their shortest path set up.

$\endgroup$
2
$\begingroup$

It depends on the implementation, but generally those edges are considered, but the algorithm immediately notices the target node is already visited or the new distance is greater than the old one, and doesn't process the edge further.

$\endgroup$
0
$\begingroup$

I've heard previously of implementations that used a visited array, but instead I simply mark each node with the starting value of Integer.MAX_VALUE or similar, of course under the assumption that no node will actually need that long of a path to get to that large of a number. Afterwards, with the condition that you only update the node if prevNode + distance < currentNode, this will work since prevNode + distance is less. Just be careful to never add anything to unvisited nodes otherwise it overflows.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.