Dijkstra Algorithm

 

#include<iostream>

#include<string.h>

#include<stdlib.h>

using namespace std;

bool known[10];

int dist[10]={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000};

int path[10];

int adj[10][10];

int start;

void printpath(int x)

{

  if(x!=start)

 {printpath(path[x]);

  cout<<" to ";

 }

 cout<<x+1;

}

int main()

{

int v,e;

cout<<"\n enter vertex and edge";

cin>>v>>e;

int i,j;

while(e--)

{

cout<<"\n enter vertices between which you want an edge";

cin>>i>>j;

cout<<"\n enter the weight";

cin>>adj[i-1][j-1];

}

 

while(1){

 

  for(i=0;i<v;i++)

  {

    dist[i]=1000;

    known[i]=false;

    path[i]=0;

  }

cout<<"\n enter source vertex";

int current;

cin>>current;

dist[current-1]=0;

start=current-1;

int min;

int flag;

for(int i=0;i<v;i++)

{

min=1000;flag=0;

  for(int j=0;j<v;j++)

 {if(dist[j]<min&&!known[j])

  {

    min=dist[j];

    current=j;

    flag=1;

  }}

  if(flag==0)

  break;

  known[current]=true;

  for(int j=0;j<v;j++)

  if(adj[current][j]>0&&!known[j])

  {

    if(dist[current]+adj[current][j]<dist[j])

  {

    dist[j]=dist[current]+adj[current][j];

    path[j]=current;

 

  }

  }

}

 

for(i=0;i<v;i++)

cout<<dist[i]<<"\t";

int x;

cout<<"\n enter vertex to find path\n";

cin>>x;

printpath(x-1);

}

}