Dijkstra's Algorithm - Revision history

Rice at 05:22, 20 March 2024

2024-03-20T05:22:47Z

← Older revision		Revision as of 05:22, 20 March 2024
Line 1:		Line 1:
			{{Infobox Algorithm\|runtime=O(VE) or O(V^2) depending on data structure\|class=[[Graph Algorithm]], [[Greedy Algorithm]]}}

	'''Dijkstra's algorithm''' is a solution to the [[Shortest Path Problem\|shortest path problem]] for graphs with positively-weighted edges.		'''Dijkstra's algorithm''' is a solution to the [[Shortest Path Problem\|shortest path problem]] for graphs with positively-weighted edges.

2024-03-09T06:06:04Z

← Older revision		Revision as of 06:06, 9 March 2024
Line 5:		Line 5:
	Dijkstra's algorithm centers around this property: ''of all the edges leaving the source, the shortest edge must be in the shortest path.''		Dijkstra's algorithm centers around this property: ''of all the edges leaving the source, the shortest edge must be in the shortest path.''

	To reach the shortest path, Dijkstra always picks the shortest edge leaving the known nodes.		To reach the shortest path, Dijkstra always picks the shortest edge
			leaving the known nodes. In each iteration, it finalizes the distance to
			a node by picking the shortest one.

	= Implementation =		= Implementation =
Line 15:		Line 17:
	pi[v] = null		pi[v] = null
	d[s] = 0		d[s] = 0
			Q = V // priority queue of nodes
	while Q is not empty:		while Q is not empty:
	u = Q.extractMin()		u = Q.extractMin()

2024-03-09T06:03:23Z

← Older revision		Revision as of 06:03, 9 March 2024
Line 1:		Line 1:
			'''Dijkstra's algorithm''' is a solution to the [[Shortest Path Problem\|shortest path problem]] for graphs with positively-weighted edges.

			= Approach: Greedy =

			Dijkstra's algorithm centers around this property: ''of all the edges leaving the source, the shortest edge must be in the shortest path.''

			To reach the shortest path, Dijkstra always picks the shortest edge leaving the known nodes.

	= Implementation =		= Implementation =
	<pre>		<pre>

2024-03-08T01:12:30Z

2024-03-08T01:11:43Z

← Older revision		Revision as of 01:11, 8 March 2024
Line 1:		Line 1:
	~~[[Category:Algorithms]]~~
	~~{{Infobox Algorithm\|class=[[Graph Algorithms]] <br> [[Shortest Path Problem]]}}<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">~~
	~~== Dijkstra's Algorithm ==~~
	~~</aside><span></span>~~
	~~== Dijkstra's Algorithm ==~~
	~~Problem: [[Shortest Path Problem]].~~

	~~The weight of edges must be positive.~~

	~~= Approach =~~
	~~Test~~
	= Implementation =		= Implementation =
			<pre>
			Dijkstra(G, w, s) {
			// initialize
			for all v in V:
			d[v] = infty
			pi[v] = null
			d[s] = 0
			while Q is not empty:
			u = Q.extractMin()
			for all v in adj[u]:
			if d[v] > d[u] + w(u,v):
			d[v] = d[u] + w(u,v)
			pi[v] = u
			</pre>

2024-03-06T01:59:10Z

← Older revision		Revision as of 01:59, 6 March 2024
Line 1:		Line 1:
	[[Category:Algorithms]]		[[Category:Algorithms]]
	{{Infobox Algorithm\|class=[[Graph Algorithms]]}}		{{Infobox Algorithm\|class=[[Graph Algorithms]] <br> [[Shortest Path Problem]]}}<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">
			== Dijkstra's Algorithm ==
			</aside><span></span>
	== Dijkstra's Algorithm ==		== Dijkstra's Algorithm ==
	Problem: [[Shortest Path Problem]].		Problem: [[Shortest Path Problem]].

2024-03-06T01:58:45Z

← Older revision		Revision as of 01:58, 6 March 2024
Line 1:		Line 1:
	[[Category:Algorithms]]		[[Category:Algorithms]]
	~~<aside~~ class=~~"portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">~~		{{Infobox Algorithm\|class=[[Graph Algorithms]]}}
	== Dijkstra's Algorithm ==		== Dijkstra's Algorithm ==
	~~</aside><span></span>~~

	~~<span></span>~~

	Problem: [[Shortest Path Problem]].		Problem: [[Shortest Path Problem]].

Line 11:		Line 7:

	= Approach =		= Approach =
	Test~~{{Infobox Algorithm\|class=[[Graph Algorithms]]}}~~		Test
	= Implementation =		= Implementation =

2024-03-06T00:44:59Z

Approach

← Older revision		Revision as of 00:44, 6 March 2024
Line 11:		Line 11:

	= Approach =		= Approach =
	{{Infobox Algorithm\|class=[[Graph Algorithms]]}}		Test{{Infobox Algorithm\|class=[[Graph Algorithms]]}}
	= Implementation =		= Implementation =

2024-03-06T00:44:43Z

← Older revision		Revision as of 00:44, 6 March 2024
Line 1:		Line 1:
	[[Category:Algorithms]]		[[Category:Algorithms]]
	~~{{Infobox~~ Algorithm~~\|class~~=~~[[Graph Algorithms]]}}~~		<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">
			== Dijkstra's Algorithm ==
			</aside><span></span>

			<span></span>

	Problem: [[Shortest Path Problem]].		Problem: [[Shortest Path Problem]].
Line 7:		Line 11:

	= Approach =		= Approach =
			{{Infobox Algorithm\|class=[[Graph Algorithms]]}}
	= Implementation =		= Implementation =

2024-03-06T00:43:09Z

← Older revision		Revision as of 00:43, 6 March 2024
Line 1:		Line 1:
	[[Category:Algorithms]]		[[Category:Algorithms]]
			{{Infobox Algorithm\|class=[[Graph Algorithms]]}}

	Problem: [[Shortest Path Problem]].		Problem: [[Shortest Path Problem]].