Dijkstra's Algorithm

Question

Post reply

Dijkstra's Algorithm

Glen Cooper

SSCommitted

Points: 1915
More actions
January 5, 2024 at 12:00 am

#4346165

Comments posted to this topic are about the item Dijkstra's Algorithm

Viewing 5 posts - 1 through 4 (of 4 total)

You must be logged in to reply to this topic. Login to reply

wagner crivelini SSC Eights! Points: 922 More actions · Answer 1

I didn't get the idea of this article.

Good to know the mathematical theory to deal with the problem.

But when you don't mention the TSQL function that handles this situation (Shortest_path), it gives me the impression it becomes a bit confusing for people who never worked with graphs in SQL Server.

I assume Shortest_path uses this algorithm. Is that correct?

Kevin Wood-419472 SSC Veteran Points: 233 More actions · Answer 2

This is a really good article showing how Dijkstra's algorithm works, except for the following statement which left me confused:

"For the same reason as before, no other path from C to A can have a lower cost. For example, C -> D -> B -> A cannot have a lower cost since the cost of D -> B can’t be smaller than the cost of C -> A, which is minimal among all neighbors."

As shown in the diagram, the cost from D->B (5) is smaller than the cost of C->A (6).

I think what you are trying to say is the the from C->D->B->A is greater than the cost from D->B->A but I can't quite follow the logic in the paragraph.

This reply was modified 3 months, 3 weeks ago by Kevin Wood-419472.
This reply was modified 3 months, 3 weeks ago by Kevin Wood-419472.

Glen Cooper SSCommitted Points: 1915 More actions · Answer 3

You're absolutely correct.

I should have said:

"For example, C -> D -> B -> A cannot have a lower cost since the cost of D -> B -> A can’t be smaller than the cost of C -> A, which is minimal among all neighbors. So, the cost of C -> D -> B -> A can’t be smaller than the cost of C -> A."

Note that this observation assumes that all costs are non-negative, so the cost of C->D must be non-negative.

Thank you for pointing this out.

The Mathematical Interpretation section is my version of Dijkstra since I never felt comfortable with explanations where non-negativity of costs is not mentioned.

By the way, can the proof be revised where the cost of sub-paths are used, instead of edges?

You'll need to assume those costs are monotonic increasing (so increasing the length of a sub-path won't decrease its cost). That way you can answers questions like "Find a path from LA to NY where you meet the fewest number of friends on your journey".

Glen Cooper SSCommitted Points: 1915 More actions · Answer 4

Thank you for this.

I didn't know that the function mimimal_path even existed.

Presumably it uses Dijkstra.

I've not used minimal paths before, but suddenly I needed it for a large HR project involving 30,000 nodes (employees).

The simple theorem and its proof are self-contained, so the rest of the article may be ignored.

It's the only way I could understand Dijkstra.