Djikstra - Revision history

Savoundg at 06:36, 11 June 2018

2018-06-11T06:36:53Z

← Older revision		Revision as of 06:36, 11 June 2018
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
	\|}		\|}

2018-06-11T06:31:10Z

← Older revision		Revision as of 06:31, 11 June 2018
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
			\|}

2018-06-11T06:09:56Z

Created page with "Djikstra is a greedy algorithm that solves the Shortest Path problem when the nodes weight are positive."

New page

Djikstra is a greedy algorithm that solves the Shortest Path problem when the nodes weight are positive.