Whats wrong with the following Dijkstra?

[Nikhar]

Hi guys, I made a graph class and the following is a program that applies dijkstra algorithm. The program is quite big but it is easy to trace the dijkstra function. Kindly help me identify the problem.

Also, I don't know how do I set a double to INFINITY. So, I have for the time being set it to 9,999. Kindly also tell me how do I set an int or double to INFINITY.


Thanks in advance.

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<functional>
#include<cstdlib>
#include<list>
#include<queue>

using namespace std;

struct vertex;

struct edge
{
    vertex *dest;
    double cost;
    edge(vertex *a=NULL, double b=0)
    {
        dest=a;
        cost=b;
    }
};

struct vertex
{
    string name;
    vector<edge> adj;
    bool mark;
    double dist;
    vertex *prev;
    vertex(string s)
    {
        name=s;
        mark=false;
        dist=9999;
    }
};

class graph
{
    public:
        typedef map<string, vertex *,less<string> > vmap;
        vmap work;
        void addvertex(const string&);
        void viewvertex();
        void addedge(const string& from, const string& to, double cost);
        void viewcostofedge(const string &from, const string &to);
        bool is_exist(const string&, const string&);
        bool pathexists(vertex *, vertex *);
        void markvertex(vertex *);
        void unmarkvertex(vertex *);
        bool ismarked(vertex *);
        void unweighted(const string&);
        void printpath(const string&);
        void printpath(const vertex&);
        void djikstra(const string&);
};

struct path
{
    vertex *dest;
    double cost;
    path( vertex *d = 0, double c = 0.0 ) : dest( d ) , cost( c ) { }
    bool operator>(path rhs) const
    {return cost>rhs.cost;}
    bool operator<(path rhs) const
    {return cost<rhs.cost;}
};

void graph::addvertex(const string &name)
{
    vmap::iterator itr=work.begin();
    itr=work.find(name);
    if(itr==work.end())
    {
        vertex *v;
        v= new vertex(name);
        work[name]=v;
        return;
    }
        cout<<"\nVertex already exists!";

}

void graph::viewvertex()
{
    vmap::iterator itr=work.begin();
    for(;itr!=work.end();itr++)
    {
        cout<<"\n"<<itr->first;
    }
}


void graph::addedge(const string& from, const string& to, double cost)
{
    vertex *f=(work.find(from)->second);
    vertex *t=(work.find(to)->second);
    edge added(t,cost);
    f->adj.push_back(added);
}


void graph::viewcostofedge(const string &from, const string &to)
{
    vmap::iterator itr=work.find(from);
    vector<edge> v=(itr->second)->adj;
    vector<edge>::iterator itr1=v.begin();
    vertex *p;
    for(;itr1!=v.end();itr1++)
    {
        if(((*itr1).dest)->name==to)
            cout<<"\nThe cost is:-"<<(*itr1).cost;
    }
}

bool graph::is_exist(const string& from, const string& to)
{
    vmap::iterator itr=work.find(from);
    vertex *v=itr->second;
    itr=work.find(to);
    vertex *w=itr->second;
    if(pathexists(v,w))
        cout<<"\nPath exists!";
    else
        cout<<"\nIt does not exist!";

}

bool graph::pathexists(vertex *v, vertex *w)
{
    if(v->name==w->name)
        return true;
    if(v!=NULL)
    {
        vector<edge>::iterator itr=(v->adj).begin();
        for(;itr!=(v->adj).end();itr++)
        {
            if(!pathexists((*itr).dest,w))
                continue;
            else
            {
                return true;
            }
        }
    }
    return false;
}

void graph::markvertex(vertex *v)
{
    v->mark=true;
}

void graph::unmarkvertex(vertex *v)
{
    v->mark=false;
}

bool graph::ismarked(vertex *v)
{
    if(v->mark==true)
        return true;
    else
        return false;
}

void graph::unweighted(const string& from)
{
    vmap::iterator itr=work.find(from);
    vertex *v=itr->second;
    list<vertex *> q;
    q.push_back(v);
    v->dist=0;
    while(!q.empty())
    {
        vertex * w=q.front();
        q.pop_front();
        for(int i=0;i<w->adj.size();i++)
        {
            edge e=w->adj[i];
            vertex *x=w->adj[i].dest;
            if(x->dist==9999)
            {
                x->dist=w->dist+1;
                x->prev=w;
                q.push_back(x);
            }
        }
    }
}

void graph::printpath(const string& name)
{
    vmap::iterator itr=work.find(name);
    vertex w=*(itr->second);
    cout<<"\nThe minimum cost is->"<<w.dist;
    cout<<"\nThe path is:-";
    printpath(w);
}

void graph::printpath(const vertex& w)
{
    if(w.prev!=NULL)
    {
        printpath(*w.prev);
        cout<<" to ";
    }
    cout<<w.name;
}

void graph::djikstra(const string& from)
{
    vmap::iterator itr=work.find(from);
    priority_queue<path, vector<path>, greater<path> > q;
    q.push(path(itr->second,0));
    path vrec;
    int nodesseen=0;
    for(;nodesseen<work.size();nodesseen++)
    {
        do
        {
                if(q.empty())
                    return;
                vrec=q.top();
                q.pop();
        }while(ismarked((q.top()).dest));
        vertex *v=vrec.dest;
        markvertex(v);
        for(int i=0;i<v->adj.size();i++)
        {
            edge e=v->adj[i];
            vertex *w=e.dest;
            if(w->dist>v->dist+e.cost)
            {
                w->dist=v->dist+e.cost;
                w->prev=v;
                q.push(path(w,w->dist));
            }
        }
    }
}

int main()
{
    int ch;

    graph g;
    string name;
    string string1,string2;
    double cost;
    do
    {
        cout<<"\n\n\n1.Add Vertex\n2.View Vertex\n3.Add Edge\n4.View Cost\n5.Path exists?"
        "\n6.Minimum length\n7.Djiksta\n8.Exit\nEnter choice:-\n";
        cin>>ch;
        switch(ch)
        {
            case 1:
                cout<<"\nEnter the name of the vertex:-";
                cin>>name;
                g.addvertex(name);
                break;
            case 2:
                g.viewvertex();
                break;
            case 3:

                cout<<"\nEnter the spot:-";
                cin>>string1;
                cout<<"\nEnter the destination!";
                cin>>string2;
                cout<<"\nEnter cost:-";
                cin>>cost;
                g.addedge(string1,string2,cost);
                break;
            case 4:

                cout<<"\nEnter the spot:-";
                cin>>string1;
                cout<<"\nEnter the destination!";
                cin>>string2;
                g.viewcostofedge(string1,string2);
                break;
            case 5:
                cout<<"\nEnter the spot:-";
                cin>>string1;
                cout<<"\nEnter the destination!";
                cin>>string2;
                g.is_exist(string1,string2);
                break;
            case 6:
                cout<<"\nEnter the spot:-";
                cin>>string1;
                cout<<"\nEnter the destination!";
                cin>>string2;
                g.unweighted(string1);
                g.printpath(string2);
                break;
            case 7:
                cout<<"\nEnter the spot:-";
                cin>>string1;
                cout<<"\nEnter the destination!";
                cin>>string2;
                g.djikstra(string1);
                g.printpath(string2);
                break;
            case 8:
                exit(0);
            default:
                cout<<"\nWrong Choice!";
        }
    }while(1);
}

[ChaseVoid]

You can try the standard limits header file, which has a list of all the possible min and max values for your system.

#include <iostream>
#include <limits>

int main(void)
{
   std::cout << std::numeric_limits<int>::max() << std::endl;
   std::cout << std::numeric_limits<double>::max() << std::endl;
   std::cout << std::numeric_limits<double>::infinity() << std::endl;
   return 0 ;
}

The above code in my system generated the following:

2147483647
1.79769e+308
inf

[Nikhar]

Ok....Thanks. Now, I know one thing f setting something to infinity.