Module 3.
2
Single Source Shortest Path
Pradnya Bhangale
[email protected]
Introduction
• Shortest path algorithms are a family of algorithms designed
to solve the shortest path problem.
• The shortest path problem is something most people have
some intuitive familiarity with: given two points, A and B, what
is the shortest path between them?
• In computer science, however, the shortest path problem can
take different forms and so different algorithms are needed to
be able to solve them all.
Introduction
• For simplicity and generality, shortest path algorithms typically
operate on some input graph, G.
• This graph is made up of a set of vertices, V, and edges, E, that
connect them.
• If the edges have weights, the graph is called a weighted
graph.
• Sometimes these edges are bidirectional and the graph is
called undirected.
• Sometimes there can be even be cycles in the graph.
Types of Shortest Path Algorithms
• There are various types of graphs (weighted, unweighted,
negative, cyclic, etc.) therefore having a single algorithm that
handles all of them efficiently is not possible.
• In order to tackle different problems, we have different
shortest-path algorithms, which can be categorized into two
categories:
• Single-source
• All-pairs
Types of Shortest Path Algorithms
Single-source
In this algorithm we determine the shortest path of all the nodes in the
graph with respect to a single node i.e. we have only one source node in
this algorithms.
• Depth-First Search (DFS)
• Breadth-First Search (BFS)
• Multi-Source BFS
• Dijkstra's algorithm
• Bellman-Ford algorithm
• Topological Sort
• A* search algorithm
• Given a graph G, with vertices V, edges E with weight function w(u,v)=wu,v and
a single source vertex, s, return the shortest paths from s to all other vertices
in V.
Types of Shortest Path Algorithms
All-pairs
• Contrary to the single source shortest path algorithm, in this
algorithm we determine the shortest path between every possible
pair of nodes.
• Floyd-Warshall algorithm
• Johnson's algorithm
• Given a graph G, with vertices V, edges E with weight
function w(u,v)=wu,v return the shortest path from u to v for
all (u,v)in V.
Applications
• Mapping software like Google or Apple maps makes use of
shortest path algorithms
• Road network, operations, and logistics research
• Computer networks, like the Internet
• Airline Flight Planning
• Social Network Analysis
Single Source Shortest Path:
Dijkstra Algorithm
• E.W. Dijkstra proposed an algorithm to solve a single source
shortest path problem with a positive weighted connected
graph.
• Dijkstra’s algorithm follows the optimal substructure property
of the shortest path and the concept of relaxation.
• It describes a multistage progressive solution that computes
the shortest paths from a source node to all other nodes in a
given graph.
Dijkstra Algorithm
Specifications for Dijkstra’s algorithm
• It applies to the weighted graph with all non-negative
weights.
• It does not work for negative weights.
• The graph must be connected.
• It is suitable for both directed and undirected graphs.
Dijkstra Algorithm
The general procedure
Dijkstra Algorithm
Example 1
• Find the shortest path from source vertex A using Dijkstra’s
algorithm.
Relaxation formulae:
if dist[v1] > dist[u] + wt[u, v1] then
dist[v1] := dist[u] + wt[u, v1]; and pred[v1] := u;
Example 1: Solution
• The given graph is a directed graph with positive weights. So
we apply Dijkstra’s algorithm to enumerate all shortest paths
from a source vertex, say a, to all other vertices b, c, d, e as
below.
• We use formulae:
dist[v1] := dist[u] + wt[u, v1];
pred[v1]:= u; ---- if dist[v1] > dist[u] + wt[u, v1].
Example 1: Solution
Example 1: Solution
Example :2
• Find Dijkstra's shortest path from vertex 1 to vertex 4 for the
following graph.
Example :2 Solution
• The given graph is a directed graph with positive weights. So
we apply Dijkstra’s algorithm to enumerate all shortest paths
from a source vertex 1 to all other vertices 2, 3, 4, 5, 6 as
below.
• We use formulae: dist[v1] := dist[u] + wt[u, v1]; pred[v1] := u;
---- if dist[v1] > dist[u] + wt[u, v1].
Example :2 Solution
Example :2 Solution
Analysis of Dijkstra Algorithm
O(V)
O(V)
O(ElogV)
O(VlogV)
Time Complexity = O(V)+O(V)+O(VlogV)
+O(ElogV)= O(ElogV)
Example: 3
Example: 4
Thank You!!
