[go: up one dir, main page]
Scribd
Upload
82 views17 pages

Single Source Shortest Paths

The document discusses several algorithms for solving shortest path problems on graphs, including Dijkstra's algorithm and Bellman-Ford algorithm for single-source shortest paths, an algorithm for shortest paths in directed acyclic graphs based on topological sorting, and the Floyd-Warshall algorithm for finding all-pairs shortest paths which runs in O(n^3) time.

Uploaded by

Anukul Gangwar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
82 views17 pages

Single Source Shortest Paths

The document discusses several algorithms for solving shortest path problems on graphs, including Dijkstra's algorithm and Bellman-Ford algorithm for single-source shortest paths, an algorithm for shortest paths in directed acyclic graphs based on topological sorting, and the Floyd-Warshall algorithm for finding all-pairs shortest paths which runs in O(n^3) time.

Uploaded by

Anukul Gangwar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 17

Single-Source Shortest Paths

In a shortest-paths problem, we are


given a weighted, directed graph G = (V,
E), with weight function w : E → R
mapping edges to real-valued-weights.
The weight of path p = v0, v1, ...,
vk is the sum of the weights of its
constituent edges:
Relaxation
• For each vertex v ε V, we maintain an attribute
d[v], which is an upper bound on the weight of a
shortest path from source s to v. We call d[v] a
shortest-path estimate. We initialize the
shortest-path estimates and predecessors by
the following Θ(V)-time procedure.
• INITIALIZE-SINGLE-SOURCE(G, s)
• 1 for each vertex v ε V[G]
• 2 do d[v] ← ∞
• 3 π[v] ← NIL
• 4 d[s] ← 0
Relaxation
• The process of relaxing an edge (u, v) consists
of testing whether we can improve the shortest
path to v found so far by going through u and, if
so, updating d[v] and π[v]. A relaxation step may
decrease the value of the shortest-path estimate
d[v] and update v's predecessor field π[v].
• The following code performs a relaxation step on
edge (u, v).
• RELAX(u, v, w)
• 1 if d[v] > d[u] + w(u, v)
• 2 then d[v] ← d[u] + w(u, v)
• 3 π[v] ← u
Relaxation
• A key technique in shortest path
algorithms is relaxation
– Idea: for all v, maintain upper bound d[v] on
(s,v)
Relax(u,v,w) {
if (d[v] > d[u]+w) then d[v]=d[u]+w;
2 2
} 5 9 5 6

Relax Relax
2 2
5 7 5 6
David Luebke
The Bellman-Ford algorithm

• The Bellman-Ford algorithm solves the single-


source shortest-paths problem in the general
case in which edge weights may be negative.
• Given a weighted, directed graph G = (V, E) with
source s and weight function w : E → R, the
Bellman-Ford algorithm returns a boolean value
indicating whether or not there is a negative-
weight cycle that is reachable from the source.
• If there is such a cycle, the algorithm indicates
that no solution exists.
• If there is no such cycle, the algorithm produces
the shortest paths and their weights.
The Bellman-Ford algorithm
• The algorithm returns TRUE if and only if the graph
contains no negative weight cycles that are reachable
from the source.

• BELLMAN-FORD(G, w, s)
• 1 INITIALIZE-SINGLE-SOURCE(G, s)
• 2 for i ← 1 to |V[G]| - 1
• 3 do for each edge (u, v) ε E[G]
• 4 do RELAX(u, v, w)
• 5 for each edge (u, v) ε E[G]
• 6 do if d[v] > d[u] + w(u, v)
• 7 then return FALSE
• 8 return TRUE
The Bellman-Ford algorithm
Dijkstra's algorithm
• Dijkstra's algorithm solves the single-
source shortest-paths problem on a
weighted, directed graph G = (V, E) for the
case in which all edge weights are
nonnegative.
• the running time of Dijkstra's algorithm is
lower than that of the Bellman-Ford
algorithm.
Dijkstra's algorithm
DIJKSTRA(G, w, s)
• 1 INITIALIZE-SINGLE-SOURCE(G, s)
• 2S←Ø
• 3 Q ← V[G]
• 4 while Q ≠ Ø
• 5 do u ← EXTRACT-MIN(Q)
• 6 S ← SU {u}
• 7 for each vertex v ε Adj[u]
• 8 do RELAX(u, v, w)
Dijkstra's algorithm
Single-source shortest paths in directed
acyclic graphs

• In this case first we will sort the vertices of DAG by using


topological sort from left to right.
• There after we will relax the edges of a weighted dag
(directed acyclic graph) G = (V, E) according to a
topological sort of its vertices.
• Shortest paths are always well defined in a dag, since
even if there are negative weight edges, no negative-
weight cycles can exist.

• If there is a path from vertex u to vertex v, then u


precedes v in the topological sort.
Single-source shortest paths in directed
acyclic graphs

DAG-SHORTEST-PATHS(G, w, s)
• 1 topologically sort the vertices of G
• 2 INITIALIZE-SINGLE-SOURCE(G, s)
• 3 for each vertex u, taken in topologically sorted
order
• 4 do for each vertex v ε Adj[u]
• 5 do RELAX(u, v, w)
The total running time of this algorithm is Θ(V + E).
Single-source shortest paths in directed
acyclic graphs
All-Pairs Shortest Paths
• In this case we consider the problem of finding shortest
paths between all pairs of vertices in a graph.
• we are given a weighted, directed graph G = (V, E) with
a weight function w : E → R that maps edges to real-
valued weights. We wish to find, for every pair of vertices
u, v εV , a shortest (least-weight) path from u to v,
where the weight of a path is the sum of the weights of
its constituent edges.
• We typically want the output in tabular form: the entry in
u's row and v's column should be the weight of a
shortest path from u to v.
All-Pairs Shortest Paths

• We can solve an all-pairs shortest-paths problem by running a


single-source shortest-paths algorithm |V| times, once for each
vertex as the source.
• If all edge weights are non negative,we can use Dijkstra's algorithm.
• If we use the linear-array implementation of the min-priority queue,
the running time is O(V^3 + V E) = O(V^3).

• If negative-weight edges are allowed, Dijkstra's algorithm can no


longer be used. Instead, we must run the slower Bellman-Ford
algorithm once from each vertex.
• The resulting running time is O(V^2E), which on a dense graph is
O(V4).
The Floyd-Warshall algorithm
• FLOYD-WARSHALL(W)
• 1 n ← rows[W]
• 2 D(0) ← W
• 3 for k ← 1 to n
• 4 do for i ← 1 to n
• 5 do for j ← 1 to n
• 6 do dij^k ← min(dij^(k-1),dik^k-1+dkj^k-1)
• 7 return D^(n)
• Running time of this procedure is Θ(n^3).

You might also like