Shortest Path Problem - Revision history

Rice at 01:32, 8 March 2024

2024-03-08T01:32:06Z

@@ Line 13: / Line 13: @@
 * Single destination problem: shortest path from all nodes to a single destination
 * Single pair problem: Shortest path between input pair
 [[Category:Algorithms]]

2024-03-06T00:04:16Z

Implementation: Bellman Ford

@@ Line 1: / Line 1: @@
 = Definitions =
-A path is a sequence of nodes <math> x_1, x_2, x_3, \ldots, x_i </math>
+A path is a sequence of nodes <math> x_1, x_2, x_3, \ldots, x_i </math>such that for all consecutive nodes, there exist an edge
 Let there be a weight assigned to each edge.
@@ Line 8: / Line 7: @@
 = Single Source Shortest Path (SSSP) =
-Given a graph <math> G(V,E), w(e) </math>, source node <math> S </math>,
+Given a graph <math> G(V,E), w(e) </math>, source node <math> S </math>, output the shortest path from the source
 == Variants ==
@@ Line 15: / Line 13: @@
 * Single destination problem: shortest path from all nodes to a single destination
 * Single pair problem: Shortest path between input pair
 [[Category:Algorithms]]

2024-03-05T03:43:50Z

← Older revision		Revision as of 03:43, 5 March 2024
Line 54:		Line 54:
	can detect it by running an extra time, since if there is a negative		can detect it by running an extra time, since if there is a negative
	cycle, the run time will improve.		cycle, the run time will improve.

			[[Category:Algorithms]]

2024-02-28T02:03:19Z

← Older revision		Revision as of 02:03, 28 February 2024
Line 26:		Line 26:
	Time complexity: <math> O(V^2 + VE) </math>		Time complexity: <math> O(V^2 + VE) </math>
	* Sparse: <math> O(V^2) </math>		* Sparse: <math> O(V^2) </math>
	* Dense:		* Dense: <math> O(V^3) </math>
	* <math> O(V^3) </math>

	<pre>		<pre>

2024-02-28T02:03:09Z

← Older revision		Revision as of 02:03, 28 February 2024
Line 26:		Line 26:
	Time complexity: <math> O(V^2 + VE) </math>		Time complexity: <math> O(V^2 + VE) </math>
	* Sparse: <math> O(V^2) </math>		* Sparse: <math> O(V^2) </math>
	* Dense: <math> O(V^3) </math>		* Dense:
			* <math> O(V^3) </math>

	<pre>		<pre>

2024-02-28T02:02:00Z

← Older revision		Revision as of 02:02, 28 February 2024
Line 24:		Line 24:
	OPT(a, n-1) = min(w(u,a) + OPT(n-1, u) for all (u, a) in E)		OPT(a, n-1) = min(w(u,a) + OPT(n-1, u) for all (u, a) in E)

	Time complexity: <math> O(V^2) </math>		Time complexity: <math> O(V^2 + VE) </math>
			* Sparse: <math> O(V^2) </math>
			* Dense: <math> O(V^3) </math>

	<pre>		<pre>
	// G: Graph with vertices (V) and edges (E)		// G: Graph with vertices (V) and edges (E)

2024-02-28T02:00:32Z

@@ Line 26: / Line 26: @@
 Time complexity: <math> O(V^2) </math>
 <pre>
-for e = 1 to n - 1:
+// G: Graph with vertices (V) and edges (E)
-    for each u in V:
+// w[e]: weight of edge e
-        OPT(u, e) = min(w(v,u) + OPT(v, e-1) for all (v, u))
+// S: starting node
-         OPT(u, e) = min(OPT(u,e), OPT(u, e-1))
+Bellman-Ford(G, w, S)
 </pre>

2024-02-28T01:49:35Z

← Older revision		Revision as of 01:49, 28 February 2024
Line 16:		Line 16:
	* Single pair problem: Shortest path between input pair		* Single pair problem: Shortest path between input pair

	== Implementation ==		== Implementation: Bellman Ford ==

	All shortest path must have <math> \leq n - 1 </math> edges. If this		All shortest path must have <math> \leq n - 1 </math> edges. If this
Line 22:		Line 22:
	therefore it is not the shortest.		therefore it is not the shortest.

	~~<pre>~~		OPT(a, n-1) = min(w(u,a) + OPT(n-1, u) for all (u, a) in E)
	OPT(a, n-1) = min(w(u,a) + OPT(n-1, u))
	~~</pre>~~

	~~where~~

	~~<math> (u, a) \in E </math>~~

	~~=== Bellman Ford Algorithm ===~~
	Time complexity: <math> O(V^2) </math>		Time complexity: <math> O(V^2) </math>
	<pre>		<pre>

2024-02-28T01:48:22Z

2024-02-28T01:47:43Z