Shortest Path Problem: Difference between revisions

From Rice Wiki
VisualWikitext
No edit summary
No edit summary
 
(4 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
outupt 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


== Implementation: Bellman Ford ==
= Suboptimality =


All shortest path must have <math> \leq n - 1 </math> edges. If this
Given <math>OPT = x_1, x_2, \ldots</math> is the shortest path.
condition is not satisfied, there is a cycle in in the path, and
therefore it is not the shortest.


OPT(a, n-1) = min(w(u,a) + OPT(n-1, u) for all (u, a) in E)
Prove that <math>A = OPT - x_1</math> is the shortest path between
<math>x_2</math> and the end.


Time complexity: <math> O(V^2 + VE) </math>
For contradiction, assume <math>A</math> is not optimal. There must be
* Sparse: <math> O(V^2) </math>
<math>B</math> such that
* Dense: <math> O(V^3) </math>


<pre>
<math>w(B) < w(A)</math>
// 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
Adding the path back, it is clear that it doesn't work.
can detect it by running an extra time, since if there is a negative
 
cycle, the run time will improve.
[[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.

Retrieved from "http://ricefriedegg.com:80/mediawiki/index.php?title=Shortest_Path_Problem&oldid=242"