DIJKSTRA ALGORITHM

Dijkstra algorithm is a shortest path algorithm to find the shortest path from source and destination in a weighted graph. In this algorithm, we began with a initial node and calculate the short distance from each node and updated the shortest path. This process continues until we reach to a destination node.

Program code of dijkstra algorithm implemented in C++

#include<iostream>

#include<vector>

#include<climits>

using namespace std;

class Node{

    unsigned m_name;

    public:

    Node(unsigned name):m_name(name){}

    int name() const { return m_name;}

    bool operator==(Node a){

        return m_name == a.m_name;

    }

    operator unsigned(){

        return m_name;

    }

};

class Arc {

    private:

        unsigned m_weight;

        Node m_from,m_to;

    public:

        Arc(Node a,Node b,unsigned weight=0):m_from(a),m_to(b),m_weight(weight){}

        unsigned weight() const { return m_weight;}

        Node to() const { return m_to; }

        Node from() const {return m_from;}

        bool operator==(const Arc& a){

            if(m_from == a.m_from && m_to == a.m_to )

                return true;

            return false;

        }

};

class Graph{

    private:

        vector<Arc> m_arc;

        int m_max;

    public:

        Graph():m_max(0){}

        void add(Node a,Node b,unsigned weight=0){

            if( a.name() > m_max-1 ) m_max = a+1;

            else if ( b.name() > m_max-1 ) m_max = b+1;

            m_arc.push_back(Arc(a,b,weight));

        }

        unsigned distance(Node a,Node b){

            if (a == b) return 0;

            Arc one(a,b),two(b,a);

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

                if( m_arc[i] == one || m_arc[i] == two )

                    return m_arc[i].weight();

            }

            return UINT_MAX;

        }

        unsigned minpath(Node a,Node b){

            bool *complete = new bool[m_max];

            unsigned *dist = new unsigned[m_max];

            for(int i=0;i<m_max;i++){

                complete[i] = false;

                dist[i] = UINT_MAX;

            }

            unsigned current = a;

            dist[current] = 0;

            complete[current] = true;

            while ( current != b ){

                unsigned leastindex;

                unsigned least = UINT_MAX;

                for(int i=0;i < m_max;i++){

                    if( complete[i] == true ) continue;

                    unsigned newdist = distance(current,i);

                    newdist += (newdist==UINT_MAX)?0:dist[current];

                    if( newdist < dist[i] )

                        dist[i] = newdist;

                    if( dist[i] < least ){

                        least = dist[i];

                        leastindex = i;

                    }

                }

                current = leastindex;

                complete[current] = true;

            }

            unsigned r = dist[b];

            delete []dist;

            delete []complete;

            return r;

        }

};

int main(){

    Graph g;

    g.add(5,1,1);

    g.add(5,2,4);

    g.add(5,3,3);

    g.add(1,2,1);

    g.add(1,4,7);

    g.add(2,3,2);

    g.add(3,4,2);

    cout << "Shortest path is: " << g.minpath(2,4) << endl; // 4

    return 0;

}