c++ - Dijkstra 算法未在邻接矩阵中找到路径

Question

出于某种原因，当我在随机生成的矩阵上运行 dijkstra 算法时，它没有找到所有节点之间的路径，即使很明显它是一个连通图。我已经打印出图表，它们总是遵循这种形式

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

现在我只使用 3*3 矩阵并试图让它正常工作。下面的代码制作了一个具有 9 个节点的邻接矩阵，并随机生成一个介于 1 和 3 之间的数字来表示边的权重。我用 4 表示无穷大。source 被硬编码为 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(即无法到达)。