Short Notes: Shortest Paths | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


Shortest Paths
Graph: nodes/vertices, and edges/arcs as pairs of nodes.
Directed graph: edges are ordered pairs of nodes.
Weighted graph: each edge (directed/undirected) has a weight.
Path between a pair of nodes V j, vk: sequence of edges with V j, vk at the two ends. 
Simple path: covers no node in it twice.
Loop: a path with the same start and end node.
Path length: number of edges in it.
Path weight: total wt of all edges in it.
Connected graph: there exists a path between every pair of nodes, no node is 
disconnected.
Complete graph: edge between every pair of nodes 
Acyclic graph: a graph with no cycles.
Topological Sort: In directed acyclic graph, sequentially order the nodes without 
violating any arc ordering. Such order is topological sort or topological order.
Biconnected graph: undirected connected graph where removal of no vertex 
disconnects the rest of the graph.
Articulation points: vertex like the ones mentioned above. So, bi-connected graphs are graphs 
without articulation points.
Strongly-connected component: a subgraph in which there is a path between every 
pair of nodes
Note: The whole graph could be strongly connected. Only a single node could form 
its own SCO.
Page 2


Shortest Paths
Graph: nodes/vertices, and edges/arcs as pairs of nodes.
Directed graph: edges are ordered pairs of nodes.
Weighted graph: each edge (directed/undirected) has a weight.
Path between a pair of nodes V j, vk: sequence of edges with V j, vk at the two ends. 
Simple path: covers no node in it twice.
Loop: a path with the same start and end node.
Path length: number of edges in it.
Path weight: total wt of all edges in it.
Connected graph: there exists a path between every pair of nodes, no node is 
disconnected.
Complete graph: edge between every pair of nodes 
Acyclic graph: a graph with no cycles.
Topological Sort: In directed acyclic graph, sequentially order the nodes without 
violating any arc ordering. Such order is topological sort or topological order.
Biconnected graph: undirected connected graph where removal of no vertex 
disconnects the rest of the graph.
Articulation points: vertex like the ones mentioned above. So, bi-connected graphs are graphs 
without articulation points.
Strongly-connected component: a subgraph in which there is a path between every 
pair of nodes
Note: The whole graph could be strongly connected. Only a single node could form 
its own SCO.
• The whole graph could be strongly connected.
• Only a single node could form its own SCO.
SCO creates partition of nodes in a graph: every node is in a SCC, & no node is 
outside all SCO’s.
A sub-graph of a SCC could be an SCC itself, although not necessarily.
Each Spanning Tree of a graph is a strongly connected component of G .
For every pair of nodes (v, w) in any Spanning Tree of a graph there exists a path v- 
>w and a path w->v.
Every spanning tree is a sub-tree of a spanning tree of a graph.
Clique: In graph theory, a clique in an undirected graph is a subset of its vertices 
such that every two vertices in the subset are connected by an edge. A maximal 
clique is the largest clique containing a given node.
Graph Algorithms:
• Graph traversal with visitor support: BFS, DFS
• Cycle detection
• Connected components
• Topological sorting
• Shortest paths: Dijkstra, Floyd-Warshall, A*
• Minimum spanning trees: Prim, Kruskal
• Flow: Minimum Cut
• Random graph generation
Single Source Shortest Paths
Shortest path problem is to determine one or more shortest path between a source 
vertex s and a target vertex t, where a set of edges are given.
Consider a directed graph G = (V, E) with non-negative edge weight and a 
distinguished source vertex, s e V . The problem is to determine the distance from 
the source vertex to every other vertex in the graph.
Dijkstra's Algorithm
• Dijksta's algorithm solves the single source shortest path problem on a 
weighted directed graph.
• It is Greedy algorithm.
• Dijkstra's algorithm starts at the source vertex, it grows a tree T , that spans all 
vertices reachable from S.
• Dijkstra's algorithm works similar to Prim's algorithm.
• It uses BFS (Breadth First Search) to find the shortest distances.
• The following simple algorithm explains the working principle of Dijkstra's 
algorithm.
Page 3


Shortest Paths
Graph: nodes/vertices, and edges/arcs as pairs of nodes.
Directed graph: edges are ordered pairs of nodes.
Weighted graph: each edge (directed/undirected) has a weight.
Path between a pair of nodes V j, vk: sequence of edges with V j, vk at the two ends. 
Simple path: covers no node in it twice.
Loop: a path with the same start and end node.
Path length: number of edges in it.
Path weight: total wt of all edges in it.
Connected graph: there exists a path between every pair of nodes, no node is 
disconnected.
Complete graph: edge between every pair of nodes 
Acyclic graph: a graph with no cycles.
Topological Sort: In directed acyclic graph, sequentially order the nodes without 
violating any arc ordering. Such order is topological sort or topological order.
Biconnected graph: undirected connected graph where removal of no vertex 
disconnects the rest of the graph.
Articulation points: vertex like the ones mentioned above. So, bi-connected graphs are graphs 
without articulation points.
Strongly-connected component: a subgraph in which there is a path between every 
pair of nodes
Note: The whole graph could be strongly connected. Only a single node could form 
its own SCO.
• The whole graph could be strongly connected.
• Only a single node could form its own SCO.
SCO creates partition of nodes in a graph: every node is in a SCC, & no node is 
outside all SCO’s.
A sub-graph of a SCC could be an SCC itself, although not necessarily.
Each Spanning Tree of a graph is a strongly connected component of G .
For every pair of nodes (v, w) in any Spanning Tree of a graph there exists a path v- 
>w and a path w->v.
Every spanning tree is a sub-tree of a spanning tree of a graph.
Clique: In graph theory, a clique in an undirected graph is a subset of its vertices 
such that every two vertices in the subset are connected by an edge. A maximal 
clique is the largest clique containing a given node.
Graph Algorithms:
• Graph traversal with visitor support: BFS, DFS
• Cycle detection
• Connected components
• Topological sorting
• Shortest paths: Dijkstra, Floyd-Warshall, A*
• Minimum spanning trees: Prim, Kruskal
• Flow: Minimum Cut
• Random graph generation
Single Source Shortest Paths
Shortest path problem is to determine one or more shortest path between a source 
vertex s and a target vertex t, where a set of edges are given.
Consider a directed graph G = (V, E) with non-negative edge weight and a 
distinguished source vertex, s e V . The problem is to determine the distance from 
the source vertex to every other vertex in the graph.
Dijkstra's Algorithm
• Dijksta's algorithm solves the single source shortest path problem on a 
weighted directed graph.
• It is Greedy algorithm.
• Dijkstra's algorithm starts at the source vertex, it grows a tree T , that spans all 
vertices reachable from S.
• Dijkstra's algorithm works similar to Prim's algorithm.
• It uses BFS (Breadth First Search) to find the shortest distances.
• The following simple algorithm explains the working principle of Dijkstra's 
algorithm.
let T be a single vertex s; 
while (T has fewer than n vertices)
f
find edge (x,y)
with x in T and y not in T 
minimizing d(s ,x)+le n g t h (s,y) 
add (x,y) to T; 
d(s,y)=d(s^s)+length(.v,y):
Dijkstra's Algorithm Implementation using Heap:
Make a heap of values (vertex,edge,distance);
Initially (v,-,infinity) for each vertex;
Let tree T be empty;
while (T has fewer than n vertices)
{
let (v,e,d(v)) have the smallest weight in the heap; 
remove (v,e,d(v)) from the heap; 
add v and e to T; 
set distance(s,v) to d(v); 
for each edge f=(v,u) 
if u is not already in T
find value (u,g,d(u)) in heap 
if d(v)+length(f) < d(g)
replace (u,e,d(e)) with (u, f d(v)+ 1 eneth(f))
1
Analysis of Dijkstra's Algorithm: Time complexity is similar to Prim's algorithm
• Using Heap : Time complexity is 0( |E| log |V|)
• Using Fibonacci Heap : Time complexity is 0(|E| + |V| log |V|)
• Using Adjacency lis t: Time complexity is 0(|V|2 )
Note: Dijkstra's algorithm does not work with negative edge weights. It is important 
to know that Dijkstra's algorithm requires that weights of all edges are non­
negative. Otherwise the procedure is not able to determine whether the shortest 
path for the node was already found or not.
Let A be the starting (source) vertex in the above graph. Then shortest distance 
from A will be selected as 2. If we want to find shortest distance from A to B , it will 
result 2 using Dijkstra's algorithm. But actual shortest distance is 1 if we choose A 
to C to B path.
Bellman Ford Algorithm
Bellman-Ford algorithm solves the single-source shortest-path problem in the 
general case in which edges of a given digraph can have negative weight as
Page 4


Shortest Paths
Graph: nodes/vertices, and edges/arcs as pairs of nodes.
Directed graph: edges are ordered pairs of nodes.
Weighted graph: each edge (directed/undirected) has a weight.
Path between a pair of nodes V j, vk: sequence of edges with V j, vk at the two ends. 
Simple path: covers no node in it twice.
Loop: a path with the same start and end node.
Path length: number of edges in it.
Path weight: total wt of all edges in it.
Connected graph: there exists a path between every pair of nodes, no node is 
disconnected.
Complete graph: edge between every pair of nodes 
Acyclic graph: a graph with no cycles.
Topological Sort: In directed acyclic graph, sequentially order the nodes without 
violating any arc ordering. Such order is topological sort or topological order.
Biconnected graph: undirected connected graph where removal of no vertex 
disconnects the rest of the graph.
Articulation points: vertex like the ones mentioned above. So, bi-connected graphs are graphs 
without articulation points.
Strongly-connected component: a subgraph in which there is a path between every 
pair of nodes
Note: The whole graph could be strongly connected. Only a single node could form 
its own SCO.
• The whole graph could be strongly connected.
• Only a single node could form its own SCO.
SCO creates partition of nodes in a graph: every node is in a SCC, & no node is 
outside all SCO’s.
A sub-graph of a SCC could be an SCC itself, although not necessarily.
Each Spanning Tree of a graph is a strongly connected component of G .
For every pair of nodes (v, w) in any Spanning Tree of a graph there exists a path v- 
>w and a path w->v.
Every spanning tree is a sub-tree of a spanning tree of a graph.
Clique: In graph theory, a clique in an undirected graph is a subset of its vertices 
such that every two vertices in the subset are connected by an edge. A maximal 
clique is the largest clique containing a given node.
Graph Algorithms:
• Graph traversal with visitor support: BFS, DFS
• Cycle detection
• Connected components
• Topological sorting
• Shortest paths: Dijkstra, Floyd-Warshall, A*
• Minimum spanning trees: Prim, Kruskal
• Flow: Minimum Cut
• Random graph generation
Single Source Shortest Paths
Shortest path problem is to determine one or more shortest path between a source 
vertex s and a target vertex t, where a set of edges are given.
Consider a directed graph G = (V, E) with non-negative edge weight and a 
distinguished source vertex, s e V . The problem is to determine the distance from 
the source vertex to every other vertex in the graph.
Dijkstra's Algorithm
• Dijksta's algorithm solves the single source shortest path problem on a 
weighted directed graph.
• It is Greedy algorithm.
• Dijkstra's algorithm starts at the source vertex, it grows a tree T , that spans all 
vertices reachable from S.
• Dijkstra's algorithm works similar to Prim's algorithm.
• It uses BFS (Breadth First Search) to find the shortest distances.
• The following simple algorithm explains the working principle of Dijkstra's 
algorithm.
let T be a single vertex s; 
while (T has fewer than n vertices)
f
find edge (x,y)
with x in T and y not in T 
minimizing d(s ,x)+le n g t h (s,y) 
add (x,y) to T; 
d(s,y)=d(s^s)+length(.v,y):
Dijkstra's Algorithm Implementation using Heap:
Make a heap of values (vertex,edge,distance);
Initially (v,-,infinity) for each vertex;
Let tree T be empty;
while (T has fewer than n vertices)
{
let (v,e,d(v)) have the smallest weight in the heap; 
remove (v,e,d(v)) from the heap; 
add v and e to T; 
set distance(s,v) to d(v); 
for each edge f=(v,u) 
if u is not already in T
find value (u,g,d(u)) in heap 
if d(v)+length(f) < d(g)
replace (u,e,d(e)) with (u, f d(v)+ 1 eneth(f))
1
Analysis of Dijkstra's Algorithm: Time complexity is similar to Prim's algorithm
• Using Heap : Time complexity is 0( |E| log |V|)
• Using Fibonacci Heap : Time complexity is 0(|E| + |V| log |V|)
• Using Adjacency lis t: Time complexity is 0(|V|2 )
Note: Dijkstra's algorithm does not work with negative edge weights. It is important 
to know that Dijkstra's algorithm requires that weights of all edges are non­
negative. Otherwise the procedure is not able to determine whether the shortest 
path for the node was already found or not.
Let A be the starting (source) vertex in the above graph. Then shortest distance 
from A will be selected as 2. If we want to find shortest distance from A to B , it will 
result 2 using Dijkstra's algorithm. But actual shortest distance is 1 if we choose A 
to C to B path.
Bellman Ford Algorithm
Bellman-Ford algorithm solves the single-source shortest-path problem in the 
general case in which edges of a given digraph can have negative weight as
long as given graph G contains no negative cycles.
• Bellman Ford not uses Greedy approach to find the shortest paths.
• The algorithm requires that the graph does not contain any cycles of negative 
length, but if it does, the algorithm is able to detect it.
Pseudo Code for Bellman Ford:
d(v[lD <-0 
For (j = 2 to n)
d(v[j]) <r- CO
G
For (i = 1 to (|V|-1) 
For each (u,v) in 
d(v) < - Min (d(
E (D
v). d(u) + l(u,v))
For each (u,v) in E 
if d(v) > d(u) + l(u,v) 
Print("Negative Cycle")
C D
Analysis of Bellman Ford Algorithm:
We assume that the algorithm is run on a graph G with /V/ nodes and /£/ edges. Let 
|V|=n, and |E|=m.
1. At the beginning, the value 0 0 is assigned to each node.This requires O(n)
2. Then we do the n-7 phases of the algorithm: one phase less than the number 
of nodes. In each phase, all edges of the graph are checked, and the distance 
value of the target node may be changed. We can interpret this check and 
assignment of a new value as one step and therefore have m steps in each 
phase. In total all phases together require m ¦ (n-1) steps. This requires 0(mn)
3. Afterwards, the algorithm checks whether there is a negative circle, for which 
he looks at each edge once. Altogether he needs m steps for the check. O(m)
Total Time complexity for Bellman Ford Algorithm: 0(m n) = 0(|E|.|V|)
Floyd - Warshall Algorithm
• It can find shortest (longest) paths among all pairs of nodes in a graph, which 
does not contain any cycles of negative length.
• It is dynamic programming algorithm.
• It can be used to detect the presence of negative cycles.
• It can find transitive closure for directed graph.
Pseudo Code for Floyd-warshall algorithm: Let n be the number of vertices in the 
graph G .
• Pred [x,y] can be used to store the reachability and will help to extract the final 
path between two vertices.
• d[n,n] will store the result for all pairs shortest paths.
• w[i, j] contains the weight of an edge (i, j) for the given graph G .
Page 5


Shortest Paths
Graph: nodes/vertices, and edges/arcs as pairs of nodes.
Directed graph: edges are ordered pairs of nodes.
Weighted graph: each edge (directed/undirected) has a weight.
Path between a pair of nodes V j, vk: sequence of edges with V j, vk at the two ends. 
Simple path: covers no node in it twice.
Loop: a path with the same start and end node.
Path length: number of edges in it.
Path weight: total wt of all edges in it.
Connected graph: there exists a path between every pair of nodes, no node is 
disconnected.
Complete graph: edge between every pair of nodes 
Acyclic graph: a graph with no cycles.
Topological Sort: In directed acyclic graph, sequentially order the nodes without 
violating any arc ordering. Such order is topological sort or topological order.
Biconnected graph: undirected connected graph where removal of no vertex 
disconnects the rest of the graph.
Articulation points: vertex like the ones mentioned above. So, bi-connected graphs are graphs 
without articulation points.
Strongly-connected component: a subgraph in which there is a path between every 
pair of nodes
Note: The whole graph could be strongly connected. Only a single node could form 
its own SCO.
• The whole graph could be strongly connected.
• Only a single node could form its own SCO.
SCO creates partition of nodes in a graph: every node is in a SCC, & no node is 
outside all SCO’s.
A sub-graph of a SCC could be an SCC itself, although not necessarily.
Each Spanning Tree of a graph is a strongly connected component of G .
For every pair of nodes (v, w) in any Spanning Tree of a graph there exists a path v- 
>w and a path w->v.
Every spanning tree is a sub-tree of a spanning tree of a graph.
Clique: In graph theory, a clique in an undirected graph is a subset of its vertices 
such that every two vertices in the subset are connected by an edge. A maximal 
clique is the largest clique containing a given node.
Graph Algorithms:
• Graph traversal with visitor support: BFS, DFS
• Cycle detection
• Connected components
• Topological sorting
• Shortest paths: Dijkstra, Floyd-Warshall, A*
• Minimum spanning trees: Prim, Kruskal
• Flow: Minimum Cut
• Random graph generation
Single Source Shortest Paths
Shortest path problem is to determine one or more shortest path between a source 
vertex s and a target vertex t, where a set of edges are given.
Consider a directed graph G = (V, E) with non-negative edge weight and a 
distinguished source vertex, s e V . The problem is to determine the distance from 
the source vertex to every other vertex in the graph.
Dijkstra's Algorithm
• Dijksta's algorithm solves the single source shortest path problem on a 
weighted directed graph.
• It is Greedy algorithm.
• Dijkstra's algorithm starts at the source vertex, it grows a tree T , that spans all 
vertices reachable from S.
• Dijkstra's algorithm works similar to Prim's algorithm.
• It uses BFS (Breadth First Search) to find the shortest distances.
• The following simple algorithm explains the working principle of Dijkstra's 
algorithm.
let T be a single vertex s; 
while (T has fewer than n vertices)
f
find edge (x,y)
with x in T and y not in T 
minimizing d(s ,x)+le n g t h (s,y) 
add (x,y) to T; 
d(s,y)=d(s^s)+length(.v,y):
Dijkstra's Algorithm Implementation using Heap:
Make a heap of values (vertex,edge,distance);
Initially (v,-,infinity) for each vertex;
Let tree T be empty;
while (T has fewer than n vertices)
{
let (v,e,d(v)) have the smallest weight in the heap; 
remove (v,e,d(v)) from the heap; 
add v and e to T; 
set distance(s,v) to d(v); 
for each edge f=(v,u) 
if u is not already in T
find value (u,g,d(u)) in heap 
if d(v)+length(f) < d(g)
replace (u,e,d(e)) with (u, f d(v)+ 1 eneth(f))
1
Analysis of Dijkstra's Algorithm: Time complexity is similar to Prim's algorithm
• Using Heap : Time complexity is 0( |E| log |V|)
• Using Fibonacci Heap : Time complexity is 0(|E| + |V| log |V|)
• Using Adjacency lis t: Time complexity is 0(|V|2 )
Note: Dijkstra's algorithm does not work with negative edge weights. It is important 
to know that Dijkstra's algorithm requires that weights of all edges are non­
negative. Otherwise the procedure is not able to determine whether the shortest 
path for the node was already found or not.
Let A be the starting (source) vertex in the above graph. Then shortest distance 
from A will be selected as 2. If we want to find shortest distance from A to B , it will 
result 2 using Dijkstra's algorithm. But actual shortest distance is 1 if we choose A 
to C to B path.
Bellman Ford Algorithm
Bellman-Ford algorithm solves the single-source shortest-path problem in the 
general case in which edges of a given digraph can have negative weight as
long as given graph G contains no negative cycles.
• Bellman Ford not uses Greedy approach to find the shortest paths.
• The algorithm requires that the graph does not contain any cycles of negative 
length, but if it does, the algorithm is able to detect it.
Pseudo Code for Bellman Ford:
d(v[lD <-0 
For (j = 2 to n)
d(v[j]) <r- CO
G
For (i = 1 to (|V|-1) 
For each (u,v) in 
d(v) < - Min (d(
E (D
v). d(u) + l(u,v))
For each (u,v) in E 
if d(v) > d(u) + l(u,v) 
Print("Negative Cycle")
C D
Analysis of Bellman Ford Algorithm:
We assume that the algorithm is run on a graph G with /V/ nodes and /£/ edges. Let 
|V|=n, and |E|=m.
1. At the beginning, the value 0 0 is assigned to each node.This requires O(n)
2. Then we do the n-7 phases of the algorithm: one phase less than the number 
of nodes. In each phase, all edges of the graph are checked, and the distance 
value of the target node may be changed. We can interpret this check and 
assignment of a new value as one step and therefore have m steps in each 
phase. In total all phases together require m ¦ (n-1) steps. This requires 0(mn)
3. Afterwards, the algorithm checks whether there is a negative circle, for which 
he looks at each edge once. Altogether he needs m steps for the check. O(m)
Total Time complexity for Bellman Ford Algorithm: 0(m n) = 0(|E|.|V|)
Floyd - Warshall Algorithm
• It can find shortest (longest) paths among all pairs of nodes in a graph, which 
does not contain any cycles of negative length.
• It is dynamic programming algorithm.
• It can be used to detect the presence of negative cycles.
• It can find transitive closure for directed graph.
Pseudo Code for Floyd-warshall algorithm: Let n be the number of vertices in the 
graph G .
• Pred [x,y] can be used to store the reachability and will help to extract the final 
path between two vertices.
• d[n,n] will store the result for all pairs shortest paths.
• w[i, j] contains the weight of an edge (i, j) for the given graph G .
Floyd-Warshall (w, n)
Analysis of Floyd - Warshall Algorithm:
1. In the beginning of code there are two loops, which requires 0 (n2 ) time and 
two statements inside the inner loop takes constant time.
2. Next, there are three loops. These three loops can require 0(n3) time. If 
statement of the inner loop requires constant time.
Time complexity of Floyd - Warshall Algorithm = 0( n3)