View source for Shortest Path Problem

= Definitions =

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.

= Single Source Shortest Path (SSSP) =

Given a graph <math> G(V,E), w(e) </math>, source node <math> S </math>, output the shortest path from the source

== Variants ==

* 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]]