In the last section, We
came across DFS, an Algorithm to be used to find out the vertices that could be
reached from a given vertex in a Graph.
Now Let’s ask ourselves
another question as well:
How do we find the
shortest path from a given vertex to any other vertex?
How does Google Maps and
other such Applications and Web Utilities manage to find out the shortest paths
and tell those to you?
The Answer is that they
use certain Algorithms such as Djikstra’s Algorithm, Floyd Warshall Algorithm,
Bellman Ford Algorithm and the like.
The first step towards
doing that is attaching a Distance/length to every edge of the Graph so that we
are able to see which is the shortest path.
Let’s start with
Djikstra’s :
We may state the problem
we want to solve formally as: Given a Graph and a vertex Compute the
Shortest Paths from that Vertex to all the other vertices present in the Graph.
Consider a Graph looks
like the following:
What we want to do is
find the shortest path from a given vertex, say vertex A to all the other
vertices present in the Graph.
Here’s the Pseudocode:
1 function
Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph: // Initialization
6 dist[v] ←
INFINITY // Unknown
distance from source to v
7 prev[v] ←
UNDEFINED // Previous
node in optimal path from source
8 add v to Q // All nodes initially in Q
(unvisited nodes)
9
10
dist[source] ← 0 // Distance from source
to source
11
12 while Q
is not empty:
13 u ←
vertex in Q with min dist[u] // Node
with the least distance will be selected first
14
remove u from Q
15
16 for
each neighbor v of u: // where
v is still in Q.
17
alt ← dist[u] +
length(u, v)
18
if alt < dist[v]:
// A shorter path to v has been found
19
dist[v] ← alt
20
prev[v] ← u
21
22 return
dist[], prev[]
It may seem striking at
first that how could such an algorithm actually compute the Shortest Paths in a
Graph, Note that dist[] is a property we associate with every vertex which
represents the distance of the particular vertex from the selected source, and
prev[] is a property we associate with every vertex to represent the previous
vertex in the optimal path from the source to that particular vertex.
The Following Image/GIF provides a nice visualization of how Djikstra's Algorithm works:
NOTE: In order for
Djikstra’s Algorithm to work, the length of all edges must be positive and the
Graph must be acylic i.e. There shouldn’t be any cyles in the Graph for Example
in the graph below, there’s a cycle: B-C-E-D-B, and thus Djikstra’s Algorithm
won’t work on this graph or any other such graph
It could be easily analysed
that Djikstra’s Algorithm is a O(V2) algorithm(where V is the number
of vertices), though when we try to optimize Djikstra’s Algorithm by using
priority queues(which is another slightly complex data structure about which you may read up on Google!), We could get a running time of O(E+V log V), where E is the
number of Edges and V is the number of vertices in the graph.
In C/C++ Code,
Djikstra’s Algorithm looks like this:
// A C / C++ program for Dijkstra's
single source shortest path algorithm.
// The program is for adjacency matrix
representation of the graph
#include <stdio.h>
#include <limits.h>
// Number of vertices in the graph
#define V 9
// A utility function to find the
vertex with minimum distance value, from
// the set of vertices not yet included
in shortest path tree
int
minDistance(int dist[], bool sptSet[])
{
// Initialize min
value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <=
min)
min
= dist[v], min_index = v;
return min_index;
}
// A utility function to print the
constructed distance array
int
printSolution(int dist[], int n)
{
printf("Vertex
Distance from Sourcen");
for (int i = 0; i < V; i++)
printf("%d
tt %dn", i, dist[i]);
}
// Funtion that implements Dijkstra's
single source shortest path algorithm
// for a graph represented using
adjacency matrix representation
void
dijkstra(int graph[V][V], int src)
{
int dist[V];
// The output array. dist[i] will hold the shortest
//
distance from src to i
bool sptSet[V]; // sptSet[i]
will true if vertex i is included in shortest
//
path tree or shortest distance from src to i is finalized
//
Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i]
= INT_MAX, sptSet[i] = false;
//
Distance of source vertex from itself is always 0
dist[src]
= 0;
// Find
shortest path for all vertices
for (int count = 0; count <
V-1; count++)
{
//
Pick the minimum distance vertex from the set of vertices not
//
yet processed. u is always equal to src in first iteration.
int u = minDistance(dist,
sptSet);
//
Mark the picked vertex as processed
sptSet[u]
= true;
//
Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++)
//
Update dist[v] only if is not in sptSet, there is an edge from
//
u to v, and total weight of path from src to v through u is
//
smaller than current value of dist[v]
if (!sptSet[v] &&
graph[u][v] && dist[u] != INT_MAX
&&
dist[u]+graph[u][v] < dist[v])
dist[v]
= dist[u] + graph[u][v];
}
// print
the constructed distance array
printSolution(dist,
V);
}
// driver program to test above
function
int
main()
{
/* Let us create the
example graph discussed above */
int graph[V][V] = {{0, 4, 0,
0, 0, 0, 0, 8, 0},
{4,
0, 8, 0, 0, 0, 0, 11, 0},
{0,
8, 0, 7, 0, 4, 0, 0, 2},
{0,
0, 7, 0, 9, 14, 0, 0, 0},
{0,
0, 0, 9, 0, 10, 0, 0, 0},
{0,
0, 4, 14, 10, 0, 2, 0, 0},
{0,
0, 0, 0, 0, 2, 0, 1, 6},
{8,
11, 0, 0, 0, 0, 1, 0, 7},
{0,
0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph,
0);
return 0;
}
NOTE: This implementation uses a slightly different
version of Graph Representation known as Adjacency Matrices. You may read more
about it at: https://goo.gl/C4MPzk
Now, Just suppose that
we had to find out the shortest routes between all pairs of two vertices
present in any graph.
We do it by the
so-called Floyd Warshall Algorithm which is named after the person who
discovered/invented it.
Here’s the pseudocode
for Floyd Warshall:
1
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2
for each vertex v
3 dist[v][v] ←
0
4
for each edge (u,v)
5 dist[u][v] ←
w(u,v) // the weight of the edge (u,v)
6
for k from 1 to |V|
7 for i from 1 to |V|
8 for j from 1 to |V|
9 if dist[i][j] > dist[i][k] +
dist[k][j]
10 dist[i][j] ←
dist[i][k] + dist[k][j]
11 end if
You may find a pretty
visualization, demonstrating what exactly happens in Floyd Warshall at: https://goo.gl/Ywq5wq
NOTE: |V| means the
number of Vertices present in the graph
It is easy to deduce that the complexity/running time of Floyd
Warshall is O(n3).
Here’s how it looks in C++ Code:
#include <iostream>
#include <conio.h>
using namespace std;
void floyds(int b[][7])
{
int i, j,
k;
for (k = 0;
k < 7; k++)
{
for (i
= 0; i < 7; i++)
{
for
(j = 0; j < 7; j++)
{
if ((b[i][k] * b[k][j] != 0) && (i != j))
{
if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0))
{
b[i][j] = b[i][k] +
b[k][j];
}
}
}
}
}
for (i = 0;
i < 7; i++)
{
cout<<"\nMinimum Cost With Respect to
Node:"<<i<<endl;
for (j
= 0; j < 7; j++)
{
cout<<b[i][j]<<"\t";
}
}
}
int main()
{
int
b[7][7];
cout<<"ENTER VALUES OF ADJACENCY MATRIX\n\n";
for (int i
= 0; i < 7; i++)
{
cout<<"enter values for "<<(i+1)<<"
row"<<endl;
for
(int j = 0; j < 7; j++)
{
cin>>b[i][j];
}
}
floyds(b);
getch();
}
NOTE: This implementation of Floyd Warshall doesn’t take a graph as
input but rather just the Matrix which represents the distances between various
nodes, set to 0 if there is no edge between the pair of vertices, the Program
sets all the 0s to Infinity(or a value synonymous to Infinity) and sets the
distance of all vertices to itself to 0.
Also, getch() is a function which returns true/false alongwith a
character depending on whether you hit it on your keyboard or not, It’s a way of
halting the program and displaying it on the screen till the point you don’t
press any key.
Please Note that Djikstra’s Algorithm is very Important to Computer
Science across all of its sectors!
Comments
Post a Comment