Dijkstra的算法問題[轉貼]

我意識到我不能在我自己的問題上發表解答，因爲我的代表低或者其他問題，所以我刪除了我的舊問題，並且正在對它進行調整。我改變了一些東西，仍然無法得到我要找的東西。Dijkstra的算法問題[轉貼]

這裏是大部分代碼我省略了一些較簡單的實現，比如pathFinder類的一部分，因爲我確定它們工作正常，這就是爲什麼你會在隨機看到playerVertex和時間的原因。在他們使用了reduceKey函數的例子中，我不確定這是我錯過了什麼嗎？我在這裏是初學者，所以建設性的批評是受歡迎的。（希望儘可能禮貌）大聲笑。我的問題是打印路徑，我得到一遍又一遍的相同的兩個值的循環。

class Heap 
{ 
public: Heap(); 
    ~Heap(); 
    void insert(double element); 
    double deletemin(); 
    void print(); 
    int size(){return heap.size();} 


private: 
int currentIndex; 
int left(int parent); 
int right(int parent); 
int parent(int child); 
void heapifyup(int index); 
void heapifydown(int index); 
private: 
vector<double> heap; 
}; 

Heap::Heap() 
{ 
currentIndex = 0; 
} 
Heap::~Heap() 
{} 

void Heap::insert(double element) 
{ 
heap.push_back(element); 
currentIndex++; 
heapifyup(heap.size() - 1); 
} 

double Heap::deletemin() 
{ 
double min = heap.front(); 
heap[0] = heap.at(heap.size()-1); 
heap.pop_back(); 
heapifydown(0); 
currentIndex--; 
return min; 
} 
void Heap::print() 
{ 
vector<double>::iterator pos = heap.begin(); 
cout << "Heap = "; 
while (pos != heap.end()) 
{ 
    cout << *pos; 
    ++pos; 
    cout << endl; 
} 
} 
void Heap::heapifyup(int index) 
{ 


while((index>0) && (parent(index) >=0) && (heap[parent(index)] > heap[index])) 
{ 
double tmp = heap[parent(index)]; 
heap[parent(index)] = heap[index]; 
heap[index] = tmp; 
index = parent(index); 


} 
} 

void Heap::heapifydown(int index) 
{ 



int child = left(index); 

if((child > 0) && (right(index) > 0) && (heap[child]>heap[right(index)])) 
{ 
child = right(index); 

} 
if(child > 0) 
{ 
double tmp = heap[index]; 
heap[index] = heap[child]; 
heap[child] = tmp; 
heapifydown(child); 
} 
} 

int Heap::left(int parent) 
{ 
int i = (parent <<1) + 1; 
return(i<heap.size()) ? i : - 1; 
} 

int Heap::right(int parent) 
{ 
int i = (parent <<1) + 2; 
return(i<heap.size()) ? i : - 1; 
} 

int Heap::parent(int child) 
{ 
if(child != 0) 
{ 
int i = (child - 1) >>1; 
return i; 
} 
return -1; 
} 



class pathFinder : public weightedGraph 
{ 

private: 

vertex* playerVertex; 
double time; 


public: 
string source; 
pathFinder() 
{ 
    playerVertex = NULL; 
    time = 0; 

} 


    void Dijkstra(int s,int t) 
{ 
    vertex *verts = findVertex(grid[s][t]); 
    Heap H; 
    for each(vertex *v in vertexList) 
    { 

     if(v->data == verts->data) 
     { 
      verts->distance = 0; 
      verts->pred = NULL; 
     } 
     v->distance = INFINITY; 
     v->pred = NULL; 
     H.insert(v->data); 
    } 
    while(H.size() != 0) 
    { 

     vertex *x = findVertex(H.deletemin()); 

     for each(edge *v in x->adjacencyList) 
     { 

      if(v->end->visited != true) 
      {  
      relax(x,v->end); 
      v->end->visited = true; 
      } 
      else 
       break; 

     } 

    } 
} 








void relax(vertex *a, vertex *b) 
{ 

    if(a->distance + weightFrom(a,b) > b->distance) 
     { 
      b->distance = a->distance + weightFrom(a,b); 
      b->pred = a; 
     } 


} 


void printPath(double dest,double dest1) 
{ 
    vertex *verta = findVertex(dest); 
    while(verta->pred->data != dest1) 
    { 
    cout<<verta->data<<endl; 
    verta = verta->pred; 
    } 
}

並且我不確定打印路徑是什麼。我剛剛使用了我之前實現的BFS算法的打印路徑。

來源

2013-04-15 user2283704

只需要任何東西！ – user2283704

'對於每個''不是標準的C++，有沒有一個宏'each'定義在某處？ –

@DavidBrown我不這麼認爲。它必須是我的Visual Studio，編譯器擴展或其他東西的一部分。 – user2283704

在你的printPath函數中，你在尋找列表的最後？

繼續運行verta = verta->pred，直到數據不等於某個值。

順便說一句，不要比較平等的雙打，因爲它不會發生。請參閱What Every Computer Scientist Should Know About Floating Point.

單步執行調試程序時會發生什麼？
（嘗試繪製鏈接以及如何遍歷它們。）

來源

2013-04-15 23:49:03

是的，就像我說過的，我使用了BFS的printPath函數，所以我不確定它是否合適。我試圖做Dijkstra的讓我們說在網格[0] [0]。然後我打印從[3] [3]從pred到pred的路徑，直到達到[0] [0]。這是BFS打印出來的。我不確定這是如何在迪克斯特拉打印出來的。 – user2283704

Dijkstra的算法問題[轉貼]

回答

相關問題