Question

Using Dijkstra algorithm to compute shortest path between two nodes in C++

Answer 1

Below is the well commented code for shortest path between two nodes using Dijikstra's algorithm.As Dijikstra's algorithm doesn't work for graphs having negative cycle so as input pass only the graphs having no negative cycle.

Time complexity: O(E*log(V))

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e15
vector< pair<ll,ll> > adj[100005];
bool visited[100005];
ll dis[100005];

int main()
{   int n,m;
    cout<<"Enter number of vertices in the graph\n";
    cin>>n;
    cout<<"Enter number of edges in the graph\n";
    cin>>m;
  
    cout<<"Enter the edges in the format x y weight_of_edge_between_x_and_y\n";
    while(m--)
    {
        ll x,y,z;
        cin>>x>>y>>z;
        adj[x].push_back(make_pair(y,z));
        adj[y].push_back(make_pair(x,z));
    }
    for(int i=1;i<=n;i++)               // declaring distance of all vertices to be inf
    {
        dis[i]=inf;
        visited[i]=false;               //initially setting all vertices to be non-visited
    }
    int x;
    cout<<"Enter the source vertex\n";
    cin>>x;
    int y;
    cout<<"Enter the destination vertex\n";
    cin>>y;
    multiset < pair<ll,ll> > mset;      //Using multiset to select vertex of minimum distance from source each time
    mset.insert(make_pair(0,x));
    dis[x]=0;
    while(!mset.empty())
    {
        pair<ll,ll> p=*mset.begin();
        mset.erase(mset.begin());
        int t=p.second;
        //q.pop();
        if(visited[t])                  //skipping this iteration if node is already visited
        continue;
        visited[t]=true;
        for(int i=0;i<adj[t].size();i++)
        {   // If t is not a infinite distance from source and if distance from source to node adjacent node of t which is not visited
            // yet is greater than dist[t]+weight of edge between t and its adjacent then update dis[adj[t][i].first]=dis[t]+adj[t][i].second;
            if(dis[t]!=inf&&!visited[adj[t][i].first]&&dis[adj[t][i].first]>dis[t]+adj[t][i].second)
            {
                dis[adj[t][i].first]=dis[t]+adj[t][i].second;
                mset.insert(make_pair(dis[adj[t][i].first],adj[t][i].first));
            }
        }
    }
    if(dis[y]==inf)
        cout<<"Destination node is unreachable from source\n";
    else
        cout<<"Shortest distance between Source and destination is: "<<dis[y]<<endl;
  
}

#include«bits/stdc++.h> using namespace std; #define 11 long long #define inf 1e15 vector< pair<11,11> > adj [ 100005]; bool visited[100005]; 1l dis[100005]; int main() int n,m; cout<<"Enter number of vertices in the graphn" cout<<"Enter number of edges in the graph\n" cout<<"Enter the edges in the format x y weight_of_edge_between_x_and_y\n"; while(m--) 1l x,y,z; adj[x].push_back (make_pair(y,z)); adj[y].push_back (make_pair(x,z)); for(int i=1;i<=n;i++) // declaring distance of all vertices to be inf dis[il-inf; visited[i]-false; /linitially setting al1 vertices to be non-visited int x cout<<"Enter the source vertex\n"; cin>> int y; cout<<"Enter the destination vertex\n"; cin>y; multiset < pair< 11,11> > mset ; mset.insert (make_pair(e,x)); dis[x]-e; while( Imset.empty)) //Using multiset to select vertex of minimum distance from source each time pair<ll,1l> p-*mset.begin); mset.erase(mset.begin()) int t-p.second //q.pop); if(visited[t]) continue; visited[t]-true; for(int i-0;i<adjit].size();i++) 1II If t is not a infinite distance from source and if distance from source to node adjacent node of t which is not visited /Iskipping this iteration if node is already visited // yet is greater than dist [t]+weight of edge between t and its adjacent then update dis[adj [t][i].first-dis[t]+adj [t][i].second; if(dis[t]!-inf&&!visited[adj[t][i].first]&&dis[adj[t][i].first] dis[t]+adj[t][i].second) dis[adjit][i].first]-dis[t]+adj[t][i].second; mset.insert(make_pair(dis[adj[t][i].first],adj[t][i].first)); if(disty]--inf) coutくく"Destination node is unreachable from source\n"; else cout<<"Shortest distance between Source and destination is: "<<disy]<endl;

Example:

Enter number of vertices in the graph Enter number of edges in the graph Enter the edges in the format x y weight of edge between x andy 1 2 5 1 3 2 3 4 1 1 46 3 5 5 Enter the source vertex Enter the destination vertex Shortest distance between Source and destination is:7