Dijkstra algorithm is a graph search algorithm that solves the problem of finding the shortest path from a point in a graph to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph at the same time, hence this problem is sometimes called the single-source shortest paths problem. Dijkstra’s algorithm, was first conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959 and hence it is named after him.

Finding the Shortest Path

There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph, G = (V,E)

  • V is a set of vertices and
  • E is a set of edges

Dijkstra’s algorithm keeps two sets of vertices:

S = the set of vertices whose shortest paths from the source have already been determined and

V-S = the remaining vertices

The other data structures needed are:

d = array of best estimates of shortest path to each vertex

pi = an array of predecessors for each vertex

The basic mode of operation is:

  1. Initialize d and pi,
  2. Set S to empty,
  3. While there are still vertices in V-S,
    1. Sort the vertices in V-S according to the current best estimate of their distance from the source,
    2. Add u, the closest vertex in V-S, to S,
    3. Relax all the vertices still in V-S connected to u

As the algorithm goes on and sees more and more vertices, it attempts to update d[v] for each vertex in the graph. The process of updating estimates is called relaxation. The worst-case running time for the Dijkstra algorithm on a graph with n nodes and m edges is O(n2) because it allows for directed cycles. It even finds the shortest paths from a source node s to all other nodes in the graph. This is basically O(n2)for node selection and O(m)for distance updates. While O(n2) is the best possible complexity for dense graphs, the complexity can be improved significantly for sparse graphs.

Example

We have two routes from node A to node F, one is from A to B,D and F, and the other one is from A to C, E, G, H and F.Now we have to find the shortest path from A to F.
Node Distance from A
B 15
C 5
D N/A
E N/A
F N/A
G N/A
H N/A

Node Distance from A
B 15
C 5
D 15+15=30
E 5+5=10
F N/A
G N/A
H N/A

Node Distance from A
B 15
C 5
D 15+15=30
E 5+5=10
F N/A
G 10+20=30
H N/A
Node Distance from A
B 15
C 5
D 15+15=30
E 5+5=10
F N/A
G 10+20=30
H 30+5=35
Node Shortest Distance from A
B 15
C 5
D 15+15=30
E 5+5=10
F N/A
G 10+20=30
H 35

C++ Implementation of Dijkstra

C++ program to solve the single source shortest path problem using Dijkstra algorithm.

#include<iostream>
#include<conio.h>
#include<stdio.h>
using namespace std;
int shortest(int ,int);
int cost[10][10],dist[20],i,j,n,k,m,S[20],v,totcost,path[20],p;
main()
{
int c;
cout <<"enter no of vertices";
cin >> n;
cout <<"enter no of edges";
cin >>m;
cout <<"\nenter\nEDGE Cost\n";
for(k=1;k<=m;k++)
{
cin >> i >> j >>c;
cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]==0)
cost[i][j]=31999;
cout <<"enter initial vertex";
cin >>v;
cout << v<<"\n";
shortest(v,n);
 }

int shortest(int v,int n)
{
int min;
for(i=1;i<=n;i++)
{
S[i]=0;
dist[i]=cost[v][i];
}
path[++p]=v;
S[v]=1;
dist[v]=0;
for(i=2;i<=n-1;i++)
{
k=-1;
min=31999;
for(j=1;j<=n;j++)
{
if(dist[j]<min && S[j]!=1)
{
min=dist[j];
k=j;
}
}
if(cost[v][k]<=dist[k])
p=1;
path[++p]=k;
for(j=1;j<=p;j++)
cout<<path[j];
cout <<"\n";
//cout <<k;
S[k]=1;
for(j=1;j<=n;j++)
if(cost[k][j]!=31999 && dist[j]>=dist[k]+cost[k][j] && S[j]!=1)
 dist[j]=dist[k]+cost[k][j];
}
}

 

Tagged with: C/C++ languageSource Code
 

One Response to Applications of Dijkstra Algorithm

  1. saraahida says:

    what should i put in the edges cost?

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

Looking for something?

Use the form below to search the site:


Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.