Dijkstra算法实现-代码不能用于较大的输入

Question

#include <iostream>
#include <list>
using namespace std;
class edge
{
    public:
        int dest;
        int dist;
        edge(int a,int b)
        {
            dest=a;
            dist=b;
        }
};
class Graph
{
    public:
        int v;      
        list<edge> *adj;
        list<int> remEdges;
        int *dist;
        int *parent;
        int src;
        Graph(int);
        void addEdge(int,int,int);
        void printEdges(int);
        bool isPresent(int);
        int findMin();
        void dijkstra(int);
};
Graph::Graph(int v)
{
    adj = new list<edge>[v];
    this->v=v;
    dist=new int(v);
    parent=new int(v);
    for(int i=0;i<v;i++)
    {
        remEdges.push_back(i);
        dist[i]=INT_MAX;
    }   
}
bool Graph::isPresent(int num)
{
    list<int> :: iterator i;
    for(i=remEdges.begin();i!=remEdges.end();i++)
        if(num==*i)
            return true;
    return false;
}
int Graph::findMin()
{
    int min=INT_MAX;
    int index=-1;
    for(int i=0;i<v;i++)
        if(dist[i]<min && isPresent(i))
        {
            min=dist[i];
            index=i;
        }
    return index;
}
void Graph :: addEdge(int i,int j,int k)
{
    adj[i].push_back(edge(j,k));
    adj[j].push_back(edge(i,k));
}
void Graph :: printEdges(int src)
{
for(int i=0;i<v;i++)
if(i!=src)
cout<<dist[i]<<" ";

}
void Graph::dijkstra(int src)
{
    dist[src]=0;
    while(!remEdges.empty())
    {
        int min=findMin();
        list<edge> :: iterator i;
        for(i=adj[min].begin();i!=adj[min].end();i++)
        {
            if(isPresent((*i).dest))
            {
            if(dist[min]+(*i).dist<dist[(*i).dest])
                dist[(*i).dest] = dist[min]+(*i).dist;
            }
            parent[(*i).dest]=min;                  
        }
        remEdges.remove(min);
    }
}

int main()
{
    Graph g(9);
    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);
    g.dijkstra(0);
    g.printEdges(0);
    cout<<endl;
    return 0;
}

代码不能用于较大的输入。

我是一个算法新手，我想通过CPP实现dijkstra算法。花了很多时间来修复代码

它在调试模式下显示正确的输出，但当直接从Run按钮执行时它不工作。

我使用DEV c++来运行代码，当驱动程序函数为

时，它执行得很好

int main()
{
    Graph g(4);
    g.addEdge(0, 1, 24);
    g.addEdge(0, 3, 20);
    g.addEdge(2, 0, 3);
    g.addEdge(3, 2, 12);
    g.dijkstra(0);
    g.printEdges(0);
    cout<<endl; 
    return 0;
}

但是当我添加太多边时，它就不起作用了。

请在这方面帮助我。

Answer 1

//You should use: 
dist=new int[v]; 
parent=new int[v];
//instead of 
//dist=new int(v);  means: dist = new int[1]; dist[0] = v;
//parent=new int(v);

使用未分配的内存会导致未定义的行为，所以这只是运气，你的代码没有因为几个顶点而崩溃。

也应该只在孩子没有被访问过的情况下设置孩子的父节点，尽管这不会导致崩溃。=)

if(isPresent((*i).dest))
{
   if(dist[min]+(*i).dist<dist[(*i).dest])
      dist[(*i).dest] = dist[min]+(*i).dist;
   parent[(*i).dest]=min;
}