main.cpp

#include <iostream>
#include <vector>

// starting node (can be anything from 0 to 9)
int START_NODE = 0;

// since int cannot represent infinity, a value high enough above anything we should encounter will be used
int HIGH_VAL = 999;

// size of adjacency matrix
int MATRIX_SIZE = 10;

int main(void) {
    /* Since the graph from the test was too simple, this program will run through
    Dijkstra's Algorithm for a graph with ten nodes given by the adjacency matrix
    given below. */

    // initialize adjacency matrix (dimensions should be the same as MATRIX_SIZE
    bool a_matrix[10][10] =
    {
    {false, true, true, false, false, false, false, false, true, false},
    {false, false, true, false, false, false, false, false, false, false},
    {false, false, false, true, false, false, false, false, true, false},
    {false, false, false, false, true, false, false, false, false, false},
    {true, false, false, false, false, true, false, true, false, true},
    {false, false, false, false, false, false, false, false, false, false,},
    {false, false, false, false, false, false, false, false, false, true},
    {false, false, false, false, false, false, true, false, false, false},
    {false, false, false, false, true, false, false, false, false, false},
    {false, false, false, false, false, true, false, false, false, false}};

    // initialize counter variables
    int i, j;

    // print matrix to terminal
    std::cout << "    Adjacency matrix: " << std::endl;
    std::cout << "    0 1 2 3 4 5 6 7 8 9" << std::endl;
    std::cout << "    - - - - - - - - - -"<< std::endl;
    for(i = 0; i < MATRIX_SIZE; i++) {
        std::cout << i << " - ";
        for(j = 0; j < MATRIX_SIZE; j++) {
            if(a_matrix[i][j]) {
                std::cout << "1 ";
            } else {
                std::cout << "0 ";
            }
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;

    // array to store distance values
    int distance[MATRIX_SIZE];
    // array to keep track of visited and unvisited nodes
    bool visited[MATRIX_SIZE];
    // array to keep track of the discovering node for each node
    int found_by[MATRIX_SIZE];

    // initialize all distances to a high number to indicate infinity (since infinity can't actually be represented as an int)
    for(i = 0; i < MATRIX_SIZE; i++) {
        distance[i] = HIGH_VAL;
    }
    // however, distance to start node from start node is 0
    distance[START_NODE] = 0;

    // all nodes are originally unvisited
    for(i = 0; i < MATRIX_SIZE; i++) {
        visited[i] = false;
    }

    // all nodes are originally not discovered (indicated by HIGH_VAL)
    for(i = 0; i < MATRIX_SIZE; i++) {
        found_by[i] = HIGH_VAL;
    }

    // flag: indicates if all nodes have been visited
    bool all_visited = false;

    // node being considered
    int current_node = START_NODE;

    while(!all_visited) {
        // loop through adjacency matrix for current node
        for(i = 0; i < MATRIX_SIZE; i++) {
            // if node is adjacent to current node
            if(a_matrix[current_node][i] && !visited[i]) {
                // update found by if not already found
                if(found_by[i] == HIGH_VAL) {
                    found_by[i] = current_node;
                }
                // if distance to node is less than recorded, update distance
                if(distance[current_node] + 1 < distance[i]) {
                    distance[i] = distance[current_node] + 1;
                }
            }
        }

        // current node is now visited
        visited[current_node] = true;

        // find shortest distance unvisited node
        int closest_distance_node = HIGH_VAL; // set high start
        for(i = 0; i < MATRIX_SIZE; i++) {
            // destination node should not have been visited yet
            if(!visited[i]) {
                if(distance[i] < closest_distance_node) {
                    closest_distance_node = i;
                }
            }
        }
        // set shortest distance node as current
        current_node = closest_distance_node;

        // if closest distance node is still HIGH_VAL, then all nodes have been visited and loop should exit
        if(closest_distance_node == HIGH_VAL) {
            all_visited = true;
        }
    }

    // get destination node from the user
    int destination_node, path_node;
    do {
        std::cout << "Enter destination node (between 0 and 9): ";
        std::cin >> destination_node;
    } while(destination_node < 0 || destination_node > 9);

    // find path from start node to destination node
    path_node = destination_node;
    std::vector <int> path;
    path.push_back(path_node);
    while(path_node != 0) { // find path backwards from current node
        path.push_back(found_by[path_node]);
        path_node = found_by[path_node];
    }

    // print distance and path to specified node
    std::cout << "Distance to node from node 0: " << distance[destination_node] << std::endl;
    std::cout << "Path (nodes): ";
    while(path.size() > 0) {
        std::cout << path.back();
        if(path.size() > 1) {
            std::cout << "->";
        }
        path.pop_back();
    }
    std::cout << std::endl;

    return(0);
}