Shortest Path Problem: Difference between revisions

From Rice Wiki
VisualWikitext
No edit summary
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 15: Line 13:
* Single destination problem: shortest path from all nodes to a single destination
* Single destination problem: shortest path from all nodes to a single destination
* Single pair problem: Shortest path between input pair
* Single pair problem: Shortest path between input pair
== Implementation: Bellman Ford ==
All shortest path must have <math> \leq n - 1 </math> edges. If this
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)
Time complexity: <math> O(V^2 + VE) </math>
* Sparse: <math> O(V^2) </math>
* Dense: <math> O(V^3) </math>
<pre>
// 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
can detect it by running an extra time, since if there is a negative
cycle, the run time will improve.


[[Category:Algorithms]]
[[Category:Algorithms]]

Revision as of 00:04, 6 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
Retrieved from "http://ricefriedegg.com:80/mediawiki/index.php?title=Shortest_Path_Problem&oldid=191"