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找到最短路徑的算法？

回答

相關問題