Dijksta's Algorithm not finding path in Adjacency Matrix

Question

For some reason when I run dijkstra's algorithm on my randomly generated matrix it does not find paths between all the nodes even though it's clear that it's a connected graph. I've printed out the graphs and they always follow this form

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

Right now I'm only working with a 3*3 matrix and am trying to get that to work properly. The below code makes a adjacency matrix with 9 nodes and randomly generates a number between 1 and 3 to represent the weights of edges. I use 4 for infinity. source is hard coded to 0 and 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

You are using 4 to represent infinite distance... but 4 is a distance that is easy to reach along a valid path. This code rejects any path with a total distance >=4, because every node starts out with a distance at most 4 (i.e. unreachable) from the source.