Dijkstra找到最短路径的算法？

所以我一直试图实现Dijkstra算法来查找图中的最短路径，但是当我走时，我遇到了几个错误。首先，这里是实际的问题和我给它的组件。Dijkstra找到最短路径的算法？

“编写一个C++函数来在图上实现Dijkstra算法，该图的实现在Moodle上，名为IntroToGraphs.zip。该函数有两个参数：起始顶点和目的顶点，打印最短路径和最短距离起始顶点到目标顶点“。

void Graph :: Dijkstra（string starting，string destination）;

顶点结构已更改为包含“visited”，“distance”和“previous”。

struct adjVertex{ 
    vertex *v; 
    int weight; 
}; 
struct vertex{ 
    std::string name; 
    bool visited; 
    int distance; 
    vertex *previous; 
    std::vector<adjVertex> adj; 
};

以下是图表类的定义：

class Graph 
{ 
    public: 
     Graph(); 
     ~Graph(); 
     void addEdge(std::string v1, std::string v2, int weight); 
     void addVertex(std::string name); 
     void displayEdges(); 
    void Dijkstra(string sourceVertex, string destinationVertex); 
    protected: 
    private: 
     std::vector<vertex> vertices; 

};

下面是我写的代码：

void Graph::Dijkstra(string starting, string destination){ 
vertex * start; 
vertex * ending; 
for(int i=0;i<vertices.size();i++){ 
    vertices[i].visited=false; 
    vertices[i].distance=INT_MAX; 
    vertices[i].previous=NULL; 
    if(vertices[i].name==starting){ 
     start=&vertices[i]; 
    } 
    if(vertices[i].name==destination){ 
     ending=&vertices[i]; 
    } 
} 
start->visited=true; 
start->distance=0; 
vector<vertex *> solved; 
vector<vertex *> path; 
vertex *tmp; 
vertex *parent; 
while(!ending->visited){ //pseudo territory 
    int minDistance=INT_MAX; 
    tmp=NULL; 
    for(int i=0;i<solved.size();i++){ 
     vertex * s=solved[i]; 
     for(int y=0;y<s->adj.size();y++){ 
      if(!s->adj[y].v->visited){ 
       s->distance=s->distance+s->adj[y].v->distance; 
       if(s->distance<minDistance){ 
        tmp=s->adj[y].v; 
        minDistance=s->distance; 
        parent=s->previous; 
       } 
      } 
     } 
    } 
} 
tmp->distance=minDistance; 
tmp->previous=parent; 
tmp->visited=true;}

我这个代码击中错误是minDistance才会是一个未知的变量在最底部，当我设置tmp->距离它。任何我需要解决的线索？

来源

2016-04-08 tschadius

在循环中声明的任何内容都被限制在该循环中，并且无法在大括号外访问。事实上，你甚至不需要循环来创建一个新的范围。 More Info

while循环内声明的变量minDistance。

来源

2016-04-08 22:09:12 Ritesh

您需要在while循环范围之外初始化minDistance。

int minDistance=INT_MAX; 
while(!ending->visited){ 
    ... 
    minDistance=someOtherValue 
    ... 
} 
tmp->distance=minDistance;

minDistance的值可以在循环内改变。

来源

2016-04-08 22:16:06 gregbert

解决也似乎从未填充。您有：

vector<vertex *> solved; 
... 
    for(int i=0;i<solved.size();i++){ 
     vertex * s=solved[i];

这些都是在哪里可以找到“解决”，并没有把任何值这么for循环不应该运行，因为solved.size（）总是等于0

案件

来源

2016-04-12 15:38:44 MolerC

Dijkstra找到最短路径的算法？

回答

相关问题