Bellman-Ford Algorithm - Revision history

Rice at 00:30, 13 March 2024

2024-03-13T00:30:32Z

← Older revision		Revision as of 00:30, 13 March 2024
Line 3:		Line 3:
	\|runtime=<math>O(V^2 E)</math>		\|runtime=<math>O(V^2 E)</math>
	\|class=[[Dynamic Programming]] <br> [[Graph Algorithms]] <br> [[Shortest Path Problem]]		\|class=[[Dynamic Programming]] <br> [[Graph Algorithms]] <br> [[Shortest Path Problem]]
	}}~~<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">~~		}}
	== Bellman-Ford Algorithm ==		== Bellman-Ford Algorithm ==
	~~</aside><span></span>~~
	The Bellman-Ford algorithm is a solution to the [[Shortest Path Problem\|shortest path problem]]. It works for graphs with real-number weights, and is capable of detecting negative edge loops.		The Bellman-Ford algorithm is a solution to the [[Shortest Path Problem\|shortest path problem]]. It works for graphs with real-number weights, and is capable of detecting negative edge loops.

Rice at 00:30, 13 March 2024

2024-03-13T00:30:13Z

← Older revision		Revision as of 00:30, 13 March 2024
Line 1:		Line 1:
	[[Category:Algorithms]]		[[Category:Algorithms]]
	{{Infobox Algorithm		{{Infobox Algorithm
	\|runtime=<math>O(V^2 + E)</math>		\|runtime=<math>O(V^2 E)</math>
	\|class=[[Dynamic Programming]] <br> [[Graph Algorithms]] <br> [[Shortest Path Problem]]		\|class=[[Dynamic Programming]] <br> [[Graph Algorithms]] <br> [[Shortest Path Problem]]
	}}		}}<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">
			== Bellman-Ford Algorithm ==
			</aside><span></span>
	The Bellman-Ford algorithm is a solution to the [[Shortest Path Problem\|shortest path problem]]. It works for graphs with real-number weights, and is capable of detecting negative edge loops.		The Bellman-Ford algorithm is a solution to the [[Shortest Path Problem\|shortest path problem]]. It works for graphs with real-number weights, and is capable of detecting negative edge loops.

Rice: /* Approach: dynamic programming */

2024-03-09T05:56:56Z

Approach: dynamic programming

← Older revision		Revision as of 05:56, 9 March 2024
Line 4:		Line 4:
	\|class=[[Dynamic Programming]] <br> [[Graph Algorithms]] <br> [[Shortest Path Problem]]		\|class=[[Dynamic Programming]] <br> [[Graph Algorithms]] <br> [[Shortest Path Problem]]
	}}		}}
			The Bellman-Ford algorithm is a solution to the [[Shortest Path Problem\|shortest path problem]]. It works for graphs with real-number weights, and is capable of detecting negative edge loops.

	= Approach: dynamic programming =		= Approach: dynamic programming =
	All shortest path must have <math> \leq \|V\| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.		All shortest path must have <math> \leq \|V\| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.

Rice: /* Recurrence */

2024-03-09T05:53:17Z

Recurrence

← Older revision		Revision as of 05:53, 9 March 2024
Line 6:		Line 6:
	= Approach: dynamic programming =		= Approach: dynamic programming =
	All shortest path must have <math> \leq \|V\| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.		All shortest path must have <math> \leq \|V\| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.

			The idea is to add one edge at a time, seeing if the edge should be included in the shortest path.

	==== Recurrence ====		==== Recurrence ====
	Let OPT(n-1, a) be the length of the shortest path from source node <math>s</math> to node <math>a</math> with at most <math>n - 1</math> edges.		Let OPT(n-1, a) be the length of the shortest path from source node <math>s</math> to node <math>a</math> with at most <math>n - 1</math> edges.

	The ~~idea~~ is to add ~~one~~ edge at ~~a time, seeing if the edge should be included~~ in the shortest path.		The main loop iterates <math> n - 1</math> times. Inside each iteration, each edge is relaxed once.

			By relaxing every edge, we add a possible edge to the shortest path. Since there is at most n - 1 edges in the shortest path, we iterate n - 1 times.

	If we don't add the edge, the length is OPT(n - 2, a)		If we don't add the edge, the length is OPT(n - 2, a)
Line 16:		Line 20:
	If we add the edge, the length would be OPT(n - 2, b) + w(b, a)		If we add the edge, the length would be OPT(n - 2, b) + w(b, a)

	OPT(a, n-1) = min(w(b,a) + OPT(n-1, b) ~~for all~~ (b, a) in E)		<math> OPT(n-1, a) = min(w(b,a) + OPT(n-2, b) \forall (b, a) \in E)</math>

	= Implementation =		= Implementation =

Rice at 00:05, 6 March 2024

2024-03-06T00:05:58Z

← Older revision		Revision as of 00:05, 6 March 2024
Line 1:		Line 1:
	[[Category:Algorithms]]		[[Category:Algorithms]]
	{{Infobox Algorithm\|runtime=O(V^2 + E)}}		{{Infobox Algorithm
			\|runtime=<math>O(V^2 + E)</math>
			\|class=[[Dynamic Programming]] <br> [[Graph Algorithms]] <br> [[Shortest Path Problem]]
			}}
	= Approach: dynamic programming =		= Approach: dynamic programming =
	All shortest path must have <math> \leq \|V\| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.		All shortest path must have <math> \leq \|V\| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.

Rice at 00:02, 6 March 2024

2024-03-06T00:02:12Z

← Older revision		Revision as of 00:02, 6 March 2024
Line 1:		Line 1:
	[[Category:Algorithms]]		[[Category:Algorithms]]
	{{Infobox Algorithm\|runtime=O(V^2 + E)}}		{{Infobox Algorithm\|runtime=O(V^2 + E)}}

	= Approach: dynamic programming =		= Approach: dynamic programming =
	All shortest path must have <math> \leq \|V\| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.		All shortest path must have <math> \leq \|V\| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.

Rice at 23:59, 5 March 2024

2024-03-05T23:59:48Z

← Older revision		Revision as of 23:59, 5 March 2024
Line 1:		Line 1:
	[[Category:Algorithms]]		[[Category:Algorithms]]
			{{Infobox Algorithm\|runtime=O(V^2 + E)}}

	= Approach: dynamic programming =		= Approach: dynamic programming =

Rice: Created page with "Category:Algorithms = Approach: dynamic programming = All shortest path must have $\leq |V| - 1$ edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest. ==== Recurrence ==== Let OPT(n-1, a) be the length of the shortest path from source node $s$ to node $a$ with at most $n - 1$ edges. The idea is to add one edge at a time, seeing if the edge should be included i..."

2024-03-05T23:58:17Z

Created page with "Category:Algorithms = Approach: dynamic programming = All shortest path must have <math> \leq |V| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest. ==== Recurrence ==== Let OPT(n-1, a) be the length of the shortest path from source node <math>s</math> to node <math>a</math> with at most <math>n - 1</math> edges. The idea is to add one edge at a time, seeing if the edge should be included i..."

New page

[[Category:Algorithms]]

= Approach: dynamic programming =
All shortest path must have <math> \leq |V| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.

==== Recurrence ====
Let OPT(n-1, a) be the length of the shortest path from source node <math>s</math> to node <math>a</math> with at most <math>n - 1</math> edges.

The idea is to add one edge at a time, seeing if the edge should be included in the shortest path.

If we don't add the edge, the length is OPT(n - 2, a)

If we add the edge, the length would be OPT(n - 2, b) + w(b, a)

OPT(a, n-1) = min(w(b,a) + OPT(n-1, b) for all (b, a) in E)

= Implementation =
Time complexity: <math> O(V^2 + VE) </math>

* Sparse: <math> O(V^2) </math>
* Dense: <math> O(V^3) </math>
<pre>
// G: Graph with vertices (V) and edges (E)
// w[e]: weight of edge e
// S: starting node
Bellman-Ford(G, w, S)
V, E = G
pi[v] = null for all v // traceback

// initialize all shortest path algo
d[v] = infty for all v
d[s] = 0
for i from 1 to |V| - 1:
for all (u,v) in E
if d[v] > d[u] + w(u, v):
d[v] = d[u] + w(u,v)
pi[v] = u;

for all (u, v) in E:
if d[v] > d[u] + w(u, v):
// has negative cycle
return false
</pre>This accounts for negative edges but not negative cycles. Bellman Ford can detect it by running an extra time, since if there is a negative cycle, the run time will improve.