Latest revision as of 01:32, 8 March 2024

Definitions

A path is a sequence of nodes $x_{1},x_{2},x_{3},\ldots ,x_{i}$ such that for all consecutive nodes, there exist an edge

Let there be a weight assigned to each edge.

Given a graph $G(V,E),w(e)$ , source node $S$ , output the shortest path from the source

Single destination problem: shortest path from all nodes to a single destination
Single pair problem: Shortest path between input pair

Given $OPT=x_{1},x_{2},\ldots$ is the shortest path.

Prove that $A=OPT-x_{1}$ is the shortest path between $x_{2}$ and the end.

For contradiction, assume $A$ is not optimal. There must be $B$ such that

$w(B)<w(A)$

Adding the path back, it is clear that it doesn't work.

@@ 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
-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
-outupt 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
+= Suboptimality =
+Given <math>OPT = x_1, x_2, \ldots</math> is the shortest path.
+Prove that <math>A = OPT - x_1</math> is the shortest path between
+<math>x_2</math> and the end.
+For contradiction, assume <math>A</math> is not optimal. There must be
+<math>B</math> such that
+<math>w(B) < w(A)</math>
+Adding the path back, it is clear that it doesn't work.
+[[Category:Algorithms]]