Djikstra: Difference between revisions
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
|- | |- | ||
|https://www.youtube.com/watch?v=_lHSawdgXpI | |https://www.youtube.com/watch?v=_lHSawdgXpI | ||
|- | |||
|https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm | |||
|} | |} | ||
Latest revision as of 06:36, 11 June 2018
Djikstra is a greedy algorithm that solves the Shortest Path problem when the nodes weight are positive.
It gives the shortest path from one node to every other nodes in the graph. This algorithm keeps a list of the total distances from the starting node to all the nodes in the graph and the list on unvisited nodes. The list of total distances is initialized to 0 for the starting node and to infinity for the other nodes. The list should be updated with the distance from the current node to its neighbour nodes. The next chosen node is the unvisited node with the smallest distance from the source. The list is updated with the distance from the current node to its neighbour nodes.
The time complexity of Djikstra is O(m n log(n)) with m the number or edges and n the number of nodes.
Resources
| https://www.youtube.com/watch?v=_lHSawdgXpI |
| https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm |