Parallel single-source shortest path algorithm - Revision history

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:57:34Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:57, 12 October 2024
Line 223:		Line 223:


	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:24:46Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:24, 12 October 2024
Line 223:		Line 223:


	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]

Citation bot: Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

2023-09-27T17:57:07Z

Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

← Previous revision		Revision as of 17:57, 27 September 2023
Line 133:		Line 133:

	=== Graph 500 ===		=== Graph 500 ===
	The third computational kernel of the [[Graph500\|Graph 500]] benchmark runs a single-source shortest path computation.<ref>{{Cite web\|url=https://graph500.org/?page_id=12#sec-7\|title=Graph 500\|last=\|first=\|date=9 March 2017\|website=~~\|url-status=live~~\|archive-url=\|archive-date=\|access-date=}}</ref> The reference implementation of the Graph 500 benchmark uses the delta stepping algorithm for this computation.		The third computational kernel of the [[Graph500\|Graph 500]] benchmark runs a single-source shortest path computation.<ref>{{Cite web\|url=https://graph500.org/?page_id=12#sec-7\|title=Graph 500\|last=\|first=\|date=9 March 2017\|website=\|archive-url=\|archive-date=\|access-date=}}</ref> The reference implementation of the Graph 500 benchmark uses the delta stepping algorithm for this computation.

	== Radius stepping algorithm ==		== Radius stepping algorithm ==

Citation bot: Alter: date, title, template type. Add: chapter, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 1490/2306

2023-08-08T11:11:33Z

Alter: date, title, template type. Add: chapter, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 1490/2306

← Previous revision		Revision as of 11:11, 8 August 2023
Line 4:		Line 4:

	== Problem definition ==		== Problem definition ==
	Let <math>G=(V,E)</math> be a directed graph with <math>\|V\|=n</math> nodes and <math>\|E\|=m</math> edges. Let <math>s</math> be a distinguished vertex (called "source") and <math>c</math> be a function assigning a non-negative real-valued weight to each edge. The goal of the single-source-shortest-paths problem is to compute, for every vertex <math>v</math> reachable from <math>s</math>, the weight of a minimum-weight path from <math>s</math> to <math>v</math>, denoted by <math>\operatorname{dist}(s,v)</math> and abbreviated <math>\operatorname{dist}(v)</math>. The weight of a path is the sum of the weights of its edges. We set <math>\operatorname{dist}(u,v):=\infty</math> if <math>v</math> is unreachable from <math>u</math>.<ref name=":0">{{Cite journal\|~~last~~=Meyer\|~~first~~=U.\|last2=Sanders\|first2=P.\|date=2003-10-01\|title=Δ-stepping: a parallelizable shortest path algorithm\|journal=Journal of Algorithms\|series=1998 European Symposium on Algorithms\|volume=49\|issue=1\|pages=114–152\|doi=10.1016/S0196-6774(03)00076-2\|issn=0196-6774\|doi-access=free}}</ref>		Let <math>G=(V,E)</math> be a directed graph with <math>\|V\|=n</math> nodes and <math>\|E\|=m</math> edges. Let <math>s</math> be a distinguished vertex (called "source") and <math>c</math> be a function assigning a non-negative real-valued weight to each edge. The goal of the single-source-shortest-paths problem is to compute, for every vertex <math>v</math> reachable from <math>s</math>, the weight of a minimum-weight path from <math>s</math> to <math>v</math>, denoted by <math>\operatorname{dist}(s,v)</math> and abbreviated <math>\operatorname{dist}(v)</math>. The weight of a path is the sum of the weights of its edges. We set <math>\operatorname{dist}(u,v):=\infty</math> if <math>v</math> is unreachable from <math>u</math>.<ref name=":0">{{Cite journal\|last1=Meyer\|first1=U.\|last2=Sanders\|first2=P.\|date=2003-10-01\|title=Δ-stepping: a parallelizable shortest path algorithm\|journal=Journal of Algorithms\|series=1998 European Symposium on Algorithms\|volume=49\|issue=1\|pages=114–152\|doi=10.1016/S0196-6774(03)00076-2\|issn=0196-6774\|doi-access=free}}</ref>

	Sequential shortest path algorithms commonly apply iterative labeling methods based on maintaining a tentative distance for all nodes; <math>\operatorname{tent}(v)</math> is always <math>\infty</math> or the weight of some path from <math>s</math> to <math>v</math> and hence an upper bound on <math>\operatorname{dist}(v)</math>. Tentative distances are improved by performing edge relaxations, i.e., for an edge <math>(v,w)\in E</math> the algorithm sets <math>\operatorname{tent}(w):=\min\{\operatorname{tent}(w), \operatorname{tent}(v)+c(v,w)\}</math>.<ref name=":0" />		Sequential shortest path algorithms commonly apply iterative labeling methods based on maintaining a tentative distance for all nodes; <math>\operatorname{tent}(v)</math> is always <math>\infty</math> or the weight of some path from <math>s</math> to <math>v</math> and hence an upper bound on <math>\operatorname{dist}(v)</math>. Tentative distances are improved by performing edge relaxations, i.e., for an edge <math>(v,w)\in E</math> the algorithm sets <math>\operatorname{tent}(w):=\min\{\operatorname{tent}(w), \operatorname{tent}(v)+c(v,w)\}</math>.<ref name=":0" />
Line 133:		Line 133:

	=== Graph 500 ===		=== Graph 500 ===
	The third computational kernel of the [[Graph500\|Graph 500]] benchmark runs a single-source shortest path computation.<ref>{{Cite web\|url=https://graph500.org/?page_id=12#sec-7\|title=Graph 500\|last=\|first=\|date=\|website=\|url-status=live\|archive-url=\|archive-date=\|access-date=}}</ref> The reference implementation of the Graph 500 benchmark uses the delta stepping algorithm for this computation.		The third computational kernel of the [[Graph500\|Graph 500]] benchmark runs a single-source shortest path computation.<ref>{{Cite web\|url=https://graph500.org/?page_id=12#sec-7\|title=Graph 500\|last=\|first=\|date=9 March 2017\|website=\|url-status=live\|archive-url=\|archive-date=\|access-date=}}</ref> The reference implementation of the Graph 500 benchmark uses the delta stepping algorithm for this computation.

	== Radius stepping algorithm ==		== Radius stepping algorithm ==
	For the radius stepping algorithm, we must assume that our graph <math>G</math> is undirected.		For the radius stepping algorithm, we must assume that our graph <math>G</math> is undirected.

	The input to the algorithm is a weighted, undirected graph, a source vertex, and a target radius value for every vertex, given as a function <math>r : V \rightarrow \mathbb{R}_+</math>.<ref name=":1">{{Cite ~~journal~~\|~~last~~=Blelloch\|~~first~~=Guy E.\|last2=Gu\|first2=Yan\|last3=Sun\|first3=Yihan\|last4=Tangwongsan\|first4=Kanat~~\|date=2016~~\|title~~=Parallel Shortest Paths Using Radius Stepping\|journal~~=Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures - ~~SPAA~~ ~~'16~~\|pages=443–454\|location=New York, New York, USA\|publisher=ACM Press\|doi=10.1145/2935764.2935765\|isbn=978-1-4503-4210-0\|doi-access=free}}</ref> The algorithm visits vertices in increasing distance from the source <math>s</math>. On each step <math>i</math>, the Radius-Stepping increments the radius centered at <math>s</math> from <math>d_{i-1}</math> to <math>d_i</math> , and settles all vertices <math>v</math> in the annulus <math>d_{i-1}<d(s,v)\leq d_i</math>.<ref name=":1" />		The input to the algorithm is a weighted, undirected graph, a source vertex, and a target radius value for every vertex, given as a function <math>r : V \rightarrow \mathbb{R}_+</math>.<ref name=":1">{{Cite book\|last1=Blelloch\|first1=Guy E.\|last2=Gu\|first2=Yan\|last3=Sun\|first3=Yihan\|last4=Tangwongsan\|first4=Kanat\|title=Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures \|chapter=Parallel Shortest Paths Using Radius Stepping \|date=2016\|pages=443–454\|location=New York, New York, USA\|publisher=ACM Press\|doi=10.1145/2935764.2935765\|isbn=978-1-4503-4210-0\|doi-access=free}}</ref> The algorithm visits vertices in increasing distance from the source <math>s</math>. On each step <math>i</math>, the Radius-Stepping increments the radius centered at <math>s</math> from <math>d_{i-1}</math> to <math>d_i</math> , and settles all vertices <math>v</math> in the annulus <math>d_{i-1}<d(s,v)\leq d_i</math>.<ref name=":1" />

	Following is the radius stepping algorithm in pseudocode:		Following is the radius stepping algorithm in pseudocode:

Cadduk: correct definition of sssp

2023-04-20T15:50:38Z

correct definition of sssp

← Previous revision		Revision as of 15:50, 20 April 2023
Line 1:		Line 1:
	A central problem in algorithmic [[graph theory]] is the [[shortest path problem]]. One of the generalizations of the shortest path problem is known as the '''single-source-shortest-paths (SSSP)''' problem, which consists of finding the shortest ~~path~~ ~~between~~ ~~every~~ ~~pair~~ of vertices in a graph. There are classical [[sequential algorithm]]s which solve this problem, such as [[Dijkstra's algorithm]]. In this article, however, we present two [[parallel algorithm]]s solving this problem.		A central problem in algorithmic [[graph theory]] is the [[shortest path problem]]. One of the generalizations of the shortest path problem is known as the '''single-source-shortest-paths (SSSP)''' problem, which consists of finding the shortest paths from a source vertex <math>s</math> to all other vertices in the graph. There are classical [[sequential algorithm]]s which solve this problem, such as [[Dijkstra's algorithm]]. In this article, however, we present two [[parallel algorithm]]s solving this problem.

	Another variation of the problem is the all-pairs-shortest-paths (APSP) problem, which also has parallel approaches: [[Parallel all-pairs shortest path algorithm]].		Another variation of the problem is the all-pairs-shortest-paths (APSP) problem, which also has parallel approaches: [[Parallel all-pairs shortest path algorithm]].

145.90.101.204: /* Delta stepping algorithm */

2023-04-13T16:22:00Z

Delta stepping algorithm

← Previous revision		Revision as of 16:22, 13 April 2023
Line 24:		Line 24:
	1 '''foreach''' <math>v \in V</math> '''do''' <math>\operatorname{tent}(v):=\infty</math>		1 '''foreach''' <math>v \in V</math> '''do''' <math>\operatorname{tent}(v):=\infty</math>
	2 <math>relax(s, 0)</math>; (Insert source node with distance 0)		2 <math>relax(s, 0)</math>; (Insert source node with distance 0)
	3 '''while''' <math>\lnot isEmpty(B)</math> '''do''' (A phase: Some queued nodes left (a))		3 '''while''' <math>\lnot isEmpty(B)</math> '''do''' (A phase: Some queued nodes left (a))
	4 <math>i:=\min\{j\geq 0: B[j]\neq \emptyset\}</math> (Smallest nonempty bucket (b))		4 <math>i:=\min\{j\geq 0: B[j]\neq \emptyset\}</math> (Smallest nonempty bucket (b))
	5 <math>R:=\emptyset</math> (No nodes deleted for bucket B[i] yet)		5 <math>R:=\emptyset</math> (No nodes deleted for bucket B[i] yet)
	6 '''while''' <math>B[i]\neq \emptyset</math> '''do''' (New phase (c))		6 '''while''' <math>B[i]\neq \emptyset</math> '''do''' (New phase (c))
	7 <math>Req:=findRequests(B[i],light)</math> (Create requests for light edges (d))		7 <math>Req:=findRequests(B[i],light)</math> (Create requests for light edges (d))
	8 <math>R:=R\cup B[i]</math> (Remember deleted nodes (e))		8 <math>R:=R\cup B[i]</math> (Remember deleted nodes (e))
	9 <math>B[i]:=\emptyset</math> (Current bucket empty)		9 <math>B[i]:=\emptyset</math> (Current bucket empty)
	10 <math>relaxRequests(Req)</math> (Do relaxations, nodes may (re)enter B[i] (f))		10 <math>relaxRequests(Req)</math> (Do relaxations, nodes may (re)enter B[i] (f))
	11 <math>Req:=findRequests(R,heavy)</math> (Create requests for heavy edges (g))		11 <math>Req:=findRequests(R,heavy)</math> (Create requests for heavy edges (g))
	12 <math>relaxRequests(Req)</math> (Relaxations will not refill B[i] (h))		12 <math>relaxRequests(Req)</math> (Relaxations will not refill B[i] (h))
	13		13

Frap: Format code

2023-01-19T10:38:15Z

Format code

C5fq2%%Z at 15:25, 4 November 2022

2022-11-04T15:25:42Z

← Previous revision		Revision as of 15:25, 4 November 2022
Line 41:		Line 41:
	18 '''foreach''' <math>(w,x)\in Req</math> '''do''' <math>relax(w,x)</math>		18 '''foreach''' <math>(w,x)\in Req</math> '''do''' <math>relax(w,x)</math>
	19		19
	20 '''Procedure''' <math>relax(w,x)</math> (Insert or move w in B if x<\operatorname{tent}(w))		20 '''Procedure''' <math>relax(w,x)</math> (Insert or move w in B if <math>x<\operatorname{tent}(w)</math>)
	21 '''if''' <math>x < \operatorname{tent}(w)</math> '''then'''		21 '''if''' <math>x < \operatorname{tent}(w)</math> '''then'''
	22 \| <math>B[\lfloor \operatorname{tent}(w)/\Delta\rfloor]:=B[\lfloor \operatorname{tent}(w)/\Delta\rfloor]\setminus \{w\} </math> (If in, remove from old bucket)		22 \| <math>B[\lfloor \operatorname{tent}(w)/\Delta\rfloor]:=B[\lfloor \operatorname{tent}(w)/\Delta\rfloor]\setminus \{w\} </math> (If in, remove from old bucket)

David Eppstein: Category:Graph algorithms

2022-10-08T05:59:13Z

Category:Graph algorithms

← Previous revision		Revision as of 05:59, 8 October 2022
Line 223:		Line 223:


	[[Category:Graph ~~theory~~]]		[[Category:Graph algorithms]]

Serols: Reverted edits by 39.50.105.233 (talk) (HG) (3.4.10)

2021-05-28T13:58:10Z

Reverted edits by 39.50.105.233 (talk) (HG) (3.4.10)

Show changes

← Previous revision		Revision as of 16:22, 13 April 2023
Line 24:		Line 24:
	1 '''foreach''' <math>v \in V</math> '''do''' <math>\operatorname{tent}(v):=\infty</math>		1 '''foreach''' <math>v \in V</math> '''do''' <math>\operatorname{tent}(v):=\infty</math>
	2 <math>relax(s, 0)</math>; (Insert source node with distance 0)		2 <math>relax(s, 0)</math>; (Insert source node with distance 0)
	3 '''while''' <math>\lnot isEmpty(B)</math> '''do''' (A phase: Some queued nodes left (a))		3 '''while''' <math>\lnot isEmpty(B)</math> '''do''' (A phase: Some queued nodes left (a))
	4 <math>i:=\min\{j\geq 0: B[j]\neq \emptyset\}</math> (Smallest nonempty bucket (b))		4 <math>i:=\min\{j\geq 0: B[j]\neq \emptyset\}</math> (Smallest nonempty bucket (b))
	5 <math>R:=\emptyset</math> (No nodes deleted for bucket B[i] yet)		5 <math>R:=\emptyset</math> (No nodes deleted for bucket B[i] yet)
	6 '''while''' <math>B[i]\neq \emptyset</math> '''do''' (New phase (c))		6 '''while''' <math>B[i]\neq \emptyset</math> '''do''' (New phase (c))
	7 <math>Req:=findRequests(B[i],light)</math> (Create requests for light edges (d))		7 <math>Req:=findRequests(B[i],light)</math> (Create requests for light edges (d))
	8 <math>R:=R\cup B[i]</math> (Remember deleted nodes (e))		8 <math>R:=R\cup B[i]</math> (Remember deleted nodes (e))
	9 <math>B[i]:=\emptyset</math> (Current bucket empty)		9 <math>B[i]:=\emptyset</math> (Current bucket empty)
	10 <math>relaxRequests(Req)</math> (Do relaxations, nodes may (re)enter B[i] (f))		10 <math>relaxRequests(Req)</math> (Do relaxations, nodes may (re)enter B[i] (f))
	11 <math>Req:=findRequests(R,heavy)</math> (Create requests for heavy edges (g))		11 <math>Req:=findRequests(R,heavy)</math> (Create requests for heavy edges (g))
	12 <math>relaxRequests(Req)</math> (Relaxations will not refill B[i] (h))		12 <math>relaxRequests(Req)</math> (Relaxations will not refill B[i] (h))
	13		13

← Previous revision		Revision as of 10:38, 19 January 2023
Line 23:		Line 23:
	Following is the delta stepping algorithm in pseudocode:		Following is the delta stepping algorithm in pseudocode:
	1 '''foreach''' <math>v \in V</math> '''do''' <math>\operatorname{tent}(v):=\infty</math>		1 '''foreach''' <math>v \in V</math> '''do''' <math>\operatorname{tent}(v):=\infty</math>
	2 <math>relax(s,0)</math>; (Insert source node with distance 0)		2 <math>relax(s, 0)</math>; (Insert source node with distance 0)
	3 '''while''' <math>\lnot isEmpty(B)</math> '''do''' (A phase: Some queued nodes left (a))		3 '''while''' <math>\lnot isEmpty(B)</math> '''do''' (A phase: Some queued nodes left (a))
	4 \| <math>i:=\min\{j\geq 0: B[j]\neq \emptyset\}</math> (Smallest nonempty bucket (b))		4 <math>i:=\min\{j\geq 0: B[j]\neq \emptyset\}</math> (Smallest nonempty bucket (b))
	5 \| <math>R:=\emptyset</math> (No nodes deleted for bucket B[i] yet)		5 <math>R:=\emptyset</math> (No nodes deleted for bucket B[i] yet)
	6 \| '''while''' <math>B[i]\neq \emptyset</math> '''do''' (New phase (c))		6 '''while''' <math>B[i]\neq \emptyset</math> '''do''' (New phase (c))
	7 \| \| <math>Req:=findRequests(B[i],light)</math> (Create requests for light edges (d))		7 <math>Req:=findRequests(B[i],light)</math> (Create requests for light edges (d))
	8 \| \| <math>R:=R\cup B[i]</math> (Remember deleted nodes (e))		8 <math>R:=R\cup B[i]</math> (Remember deleted nodes (e))
	9 \| \| <math>B[i]:=\emptyset</math> (Current bucket empty)		9 <math>B[i]:=\emptyset</math> (Current bucket empty)
	10 \| \| <math>relaxRequests(Req)</math> (Do relaxations, nodes may (re)enter B[i] (f))		10 <math>relaxRequests(Req)</math> (Do relaxations, nodes may (re)enter B[i] (f))
	11 \| <math>Req:=findRequests(R,heavy)</math> (Create requests for heavy edges (g))		11 <math>Req:=findRequests(R,heavy)</math> (Create requests for heavy edges (g))
	12 \| <math>relaxRequests(Req)</math> (Relaxations will not refill B[i] (h))		12 <math>relaxRequests(Req)</math> (Relaxations will not refill B[i] (h))
	13		13
	14 '''~~Function~~''' <math>findRequests(V',kind:\{\text{light}, \text{heavy}\})</math>:set of Request		14 '''function''' <math>findRequests(V',kind:\{\text{light}, \text{heavy}\})</math>:set of Request
	15 '''return''' <math>\{(w, \operatorname{tent}(v)+c(v,w)): v\in V' \land (v,w) \in E_\text{kind}\}</math>		15 '''return''' <math>\{(w, \operatorname{tent}(v)+c(v,w)): v\in V' \land (v,w) \in E_\text{kind}\}</math>
	16		16
	17 '''~~Procedure~~''' <math>relaxRequests(Req)</math>		17 '''procedure''' <math>relaxRequests(Req)</math>
	18 '''foreach''' <math>(w,x)\in Req</math> '''do''' <math>relax(w,x)</math>		18 '''foreach''' <math>(w, x)\in Req</math> '''do''' <math>relax(w,x)</math>
	19		19
	20 '''~~Procedure~~''' <math>relax(w,x)</math> (Insert or move w in B if <math>x<\operatorname{tent}(w)</math>)		20 '''procedure''' <math>relax(w,x)</math> (Insert or move w in B if <math>x<\operatorname{tent}(w)</math>)
	21 '''if''' <math>x < \operatorname{tent}(w)</math> '''then'''		21 '''if''' <math>x < \operatorname{tent}(w)</math> '''then'''
	22 \| <math>B[\lfloor \operatorname{tent}(w)/\Delta\rfloor]:=B[\lfloor \operatorname{tent}(w)/\Delta\rfloor]\setminus \{w\} </math> (If in, remove from old bucket)		22 <math>B[\lfloor \operatorname{tent}(w)/\Delta\rfloor]:=B[\lfloor \operatorname{tent}(w)/\Delta\rfloor]\setminus \{w\} </math> (If in, remove from old bucket)
	23 \| <math>B[\lfloor x/\Delta\rfloor]:=B[\lfloor x/\Delta\rfloor]\cup \{w\} </math> (Insert into new bucket)		23 <math>B[\lfloor x/\Delta\rfloor]:=B[\lfloor x/\Delta\rfloor]\cup \{w\} </math> (Insert into new bucket)
	24 \| <math>\operatorname{tent}(w):=x </math>		24 <math>\operatorname{tent}(w):=x </math>

	=== Example ===		=== Example ===
Line 146:		Line 146:
	2 '''foreach''' <math>v \in N(s)</math> '''do''' <math>\delta(v)\leftarrow w(s,v)</math>, <math>S_0\leftarrow \{s\}</math>, <math>i \leftarrow 1</math>		2 '''foreach''' <math>v \in N(s)</math> '''do''' <math>\delta(v)\leftarrow w(s,v)</math>, <math>S_0\leftarrow \{s\}</math>, <math>i \leftarrow 1</math>
	3 '''while''' <math>\|S_{i-1}\|<\|V\|</math> '''do'''		3 '''while''' <math>\|S_{i-1}\|<\|V\|</math> '''do'''
	4 \| <math>d_i\leftarrow \min_{v\in V\setminus S_{i-1}}\{\delta(v) + r(v)\}</math>		4 <math>d_i\leftarrow \min_{v\in V\setminus S_{i-1}}\{\delta(v) + r(v)\}</math>
	5 \| '''repeat'''		5 '''repeat'''
	6 \| \| '''foreach''' <math>u \in V\setminus S_{i-1}</math> s.t <math>\delta(u) \leq d_i</math> '''do'''		6 '''foreach''' <math>u \in V\setminus S_{i-1}</math> s.t <math>\delta(u) \leq d_i</math> '''do'''
	7 \| \| \| '''foreach''' <math>v \in N(u)\setminus S_{i-1}</math> '''do'''		7 '''foreach''' <math>v \in N(u)\setminus S_{i-1}</math> '''do'''
	8 \| \| \| \| <math>\delta(v) \leftarrow \min\{\delta(v), \delta(u)+w(u,v)\}</math>		8 <math>\delta(v) \leftarrow \min\{\delta(v), \delta(u)+w(u,v)\}</math>
	9 \| '''until''' no <math>\delta(v)\leq d_i</math> was updated		9 '''until''' no <math>\delta(v)\leq d_i</math> was updated
	10 \| ''<math>S_i=\{v\;\|\;\delta(v)\leq d_i\}</math>''		10 ''<math>S_i=\{v\;\|\;\delta(v)\leq d_i\}</math>''
	11 \| <math>i=i+1</math>		11 <math>i=i+1</math>
	12 '''return''' <math>\delta(\cdot)</math>		12 '''return''' <math>\delta(\cdot)</math>
	For all <math>S\subseteq V</math>, define <math>N(S)=\bigcup_{u\in S}\{v\in V\mid d(u,v)\in E\}</math> to be the '''neighbor set''' of S. During the execution of standard [[breadth-first search]] or [[Dijkstra's algorithm]], the '''frontier''' is the neighbor set of all visited vertices.<ref name=":1" />		For all <math>S\subseteq V</math>, define <math>N(S)=\bigcup_{u\in S}\{v\in V\mid d(u,v)\in E\}</math> to be the '''neighbor set''' of S. During the execution of standard [[breadth-first search]] or [[Dijkstra's algorithm]], the '''frontier''' is the neighbor set of all visited vertices.<ref name=":1" />