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 5 (of 5 total)
You must be logged in to reply to this topic. Login to reply
This website stores cookies on your computer.
These cookies are used to improve your website experience and provide more personalized services to you, both on this website and through other media.
To find out more about the cookies we use, see our Privacy Policy