Dijkstra’s algorithm: shortest path finding algorithm

Dijkstra’s algorithm is an algorithm for finding the shortest path between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstrain 1956 and published three years later.

WORLD OF PATH FINDING.

modern day route search .

Basically the algorithm finds it’s use greatly in modern route finding system’s.

To understand this algorithm we might need to know basics of Graph theory .

Now when we are ready to draw matrix representations or edge representations of a graph diagram, we are probably all set to crack this algorithm.

THE PROBLEM

we should directly start from an solved example to understand the algorithm.

the following example is inherited from a training material example of Indian Computing Olympiad.

in the above diagram we see 7 distinct points,each representing a node.

the numbers mentioned above each line is the distance between the two joined points. Now the goal is to find the shortest route from 1 to every other point. To get a feel of realism we assume each point as a city. So basically we are trying to find the cheapest path to travel to every other city from city 1.

Now to draw the matrix table we would take to use a sort of BFS method.

Now to start with we assume to have visited no city yet, we would just draw the initial table fora a initial scenario where distance of city 1 from itself is 0 and from every other city is infinity(INF).

Now we dare to visit our home city 1 , and simultaneously mark the distance of its neighbours (the one’s connected to it).

After we are done so we compare the neighbours , and we see that city 2 is the closest, so we now raid upon 2 and similarly update the distance of it’s neighbours.

Now i guess we are making sense, and the process just continues till we have covered the whole set.We visit 3.

Next 5,

Next it’s 7,

next 6,

now since no further update is available , we visit 4.

SOLUTION CODE

To implement this method we are going to use c++ . so fasten your ide’s and get ready to run the code.

#include <iostream>
#include<vector>
using namespace std;

#define INF 10000000
int get_min_index(vector<int> dist, vector<int> visit)
{
int min= INF;
int min_index = -1;

for(int i=0;i<dist.size();i++)
{

if(dist[i]<=min && !visit[i])
{
min_index=i;
min=dist[i];
}

}
return min_index;
}
int main()
{

int n=7;
vector<vector<int>> v =
{
{0,100,800,INF,INF,INF,INF},
{100,0,60,INF,200,INF,INF},
{800,60,0,700,INF,INF,INF},
{INF,INF,700,0,INF,INF,INF},
{INF,200,INF,INF,0,500,100},
{INF,INF,INF,INF,500,0,50},
{INF,INF,INF,INF,100,50,0}
};

vector<int> dist(n,INF);
dist[0]=0;
vector<int> visit(n,0);
for(int i=0;i!=-1;i=get_min_index(dist,visit))
{
for(int j=0;j<n;j++)
{
dist[j]=min(dist[j],v[i][j]+dist[i]);

}

visit[i]=1;
}

for(int i=0;i<dist.size();i++)
cout<<”\ndistance from node”<< i << “ “<<dist[i];
for(int i=0;i<dist.size();i++)
cout<<”\nvisit from node”<< i << “ “<<visit[i];
}

now if we run the above code we get an output as such.

REPLACEMENTS TO dijkstra

A* algorithm is considered somewhat superior to dijkstra , reason being that it travels less graph path(probably) to calculate the same.

Bellman-ford’s algorithm can also be a good choice against dijkstra.

yet the simplicity and versatility of dijkstra still remains the reason to use it on a first thought.