January 5, 2024 at 12:00 am
Comments posted to this topic are about the item Dijkstra's Algorithm
January 5, 2024 at 3:40 pm
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?
January 5, 2024 at 4:33 pm
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.
January 5, 2024 at 5:36 pm
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".
January 5, 2024 at 5:45 pm
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.
Viewing 5 posts - 1 through 4 (of 4 total)
You must be logged in to reply to this topic. Login to reply