Shortest Path Problem: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
(11 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
= Definitions = | = 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. | Let there be a weight assigned to each edge. | ||
Line 8: | Line 7: | ||
= Single Source Shortest Path (SSSP) = | = 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 == | == Variants == | ||
Line 16: | Line 14: | ||
* Single pair problem: Shortest path between input pair | * 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]] |
Latest revision as of 01:32, 8 March 2024
Definitions
A path is a sequence of nodes 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 , source node , 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 is the shortest path.
Prove that is the shortest path between and the end.
For contradiction, assume is not optimal. There must be such that
Adding the path back, it is clear that it doesn't work.