Dijksta算法沒有在鄰接矩陣中找到路徑

Question

由於某些原因，當我在我的隨機生成的矩陣上運行dijkstra算法時，即使明確表示它是連通圖，它也找不到所有節點之間的路徑。我打印出來的圖形，他們始終遵循這種形式

0--2--3 
| | | 
4--5--6 
| | | 
7--8--9 

現在我只能用一個3×3的矩陣工作，我試圖獲取正常工作。下面的代碼構造了一個具有9個節點的鄰接矩陣，並隨機生成1到3之間的數字來表示邊的權重。我用無窮大4。 源是硬編碼爲0和numOfVertices 9

#include<iostream> 
#include <time.h> 
#include <math.h> 
#define INFINITY 4 
#define V 9 
using namespace std; 
class Dijkstra{  
private:   

    int predecessor[20],distance[20];   
    bool mark[20];  
    int source; 
    int destination; 
    int numOfVertices; 
    char gameMode; 

public: 
    int adjMatrix[9][9];  
    void read();   
    void initialize(); 
    void setSource(int k);  
    int getClosestUnmarkedNode();  
    void calculateDistance();   
    void output();  
    int randomEdge(); 
    int randomNode(); 
    void printPath(int); 
};  

void Dijkstra::read(){ 
    numOfVertices = 4; 
    for(int i = 0; i < numOfVertices;i++){ 
     for(int j = 0; j < numOfVertices;j++){ 
      if(i == j) 
       adjMatrix[i][j] = 0; 
      else if(j >= i){ 
       if(j == i + 1 || j == i - 1 || j == i + sqrt((double)numOfVertices)|| j == i - sqrt((double)numOfVertices)) 
        adjMatrix[i][j] = randomEdge(); 
       else 
        adjMatrix[i][j] = 4; 
       if((i % ((int)sqrt((double)numOfVertices)) == ((int)sqrt((double)numOfVertices)) - 1) && j == i + 1) 
        adjMatrix[i][j] = 4; 
      } 
      else 
       adjMatrix[i][j] = adjMatrix[j][i]; 
      cout<<adjMatrix[i][j]<< " "; 
     } 
     cout<< "\n"; 
    } 
    source = 0; 
} 
void Dijkstra::initialize(){ 
    for(int i=0;i<numOfVertices;i++) { 
     mark[i] = false; 
     predecessor[i] = -1; 
     distance[i] = INFINITY; 
    }  
    distance[source]= 0; 
}  
int Dijkstra::getClosestUnmarkedNode(){ 

    int minDistance = INFINITY; 
    int closestUnmarkedNode = 0; 
    for(int i=0;i<numOfVertices;i++) { 
     if((!mark[i]) && (minDistance >= distance[i])) { 
      minDistance = distance[i];  
      closestUnmarkedNode = i;  
     } 
    }  
    return closestUnmarkedNode; 
}  
void Dijkstra::calculateDistance(){ 
    initialize(); 
    int minDistance = INFINITY; 
    int closestUnmarkedNode; 
    int count = 0; 
    while(count < numOfVertices) {  
     closestUnmarkedNode = getClosestUnmarkedNode(); 
     mark[closestUnmarkedNode] = true; 
     for(int i=0;i<numOfVertices;i++) { 
      if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0)) { 
       if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) { 
        distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]; 
        predecessor[i] = closestUnmarkedNode;  
       }  
      }  
     }  
     count++; 
    } 
} 
void Dijkstra::printPath(int node){ 
    if(node == source) 
     cout<<node<<".."; 
    else if(predecessor[node] == -1) 
     cout<<"No path from "<<source<<"to "<<node<<endl; 
    else { 
     printPath(predecessor[node]); 
     cout<<node<<".."; 
    } 
} 
void Dijkstra::output(){ 
    for(int i=0;i<numOfVertices;i++) { 
     if(i == source) 
      cout<<source<<".."<<source; 
     else 
      printPath(i); 
     cout<<"->"<<distance[i]<<endl; 
    } 
} 
int Dijkstra::randomEdge(){ 
    return rand() % 3 + 1; 
} 
void Dijkstra::setSource(int k){ 
    source = k; 
} 
int main(int argc, char** argv){ 
    Dijkstra G; 
    G.read(); 
    G.calculateDistance(); 
    G.output(); 
    int k; 
    cin>> k; 
    exit(0); 
} 

Answer 1

您正在使用4代表無窮遠......但4一段距離，很容易沿着一個有效的路徑到達。該代碼拒絕總距離大於等於4的任何路徑，因爲每個節點的起始距離最多爲4（即不可達）。