Djikstra: Difference between revisions
Created page with "Djikstra is a greedy algorithm that solves the Shortest Path problem when the nodes weight are positive." |
No edit summary |
||
| Line 1: | Line 1: | ||
Djikstra is a greedy algorithm that solves the Shortest Path problem when the nodes weight are positive. | 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 == | |||
{| class="wikitable" | |||
! | |||
|- | |||
|https://www.youtube.com/watch?v=_lHSawdgXpI | |||
|} | |||
Revision as of 06:31, 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 |