dijkstra-shortest-path-algorithm/shortest_path.cpp

#include "shortest_path.h"

// destructor
Shortest_Path::~Shortest_Path() {}

// helper to get node with minimal src->node distance
int Shortest_Path::min_node_index()
{
    int min_index = 0;
    int i = 0;

    // find first unvisited node and set its min_index;
    for (; i < graph.V; i++) {
        if (!graph.visited[i]) {
            min_index = i, i++;
            break;
        }
    }

    // continue with next index
    for (;i < graph.V; i++) {
        if (!graph.visited[i] && graph.src_node_dist[i] < graph.src_node_dist[min_index])
            min_index = i;
    }

    return min_index;
}

// calculate shortest path between two nodes
float Shortest_Path::calculate_path(int src, int dest)
{
    // reset shortest_path configuration from previous calculation
    reset_shortest_path();

    // reset graph calculation helper members to default for a new calculation
    graph.reset_path_calculation();

    // initialize src->src distance to 0, all other are infinite
    graph.src_node_dist[src] = 0;

    int u; // to store current node index
    while(graph.unvisited) {
        u = min_node_index(); // get next min value index

        // if we reach a destination node we quit
        if (u == dest) {
            graph.visited[u] = true;
            graph.subtract_unvisited();
            break;
        }

        // find current node neighbours
        for (int i = 0; i < graph.V; i++) {
            // if there is connection between node and its unvisited neighbour
            if (graph.graph_matrix[u][i] != 0 && !graph.visited[i]) {
                // compute the distance from source (curent node distance plus edge to the neighbour)
                // update the distance if it is less than known distance in src_to_node_distances
                if (graph.src_node_dist[u] + graph.graph_matrix[u][i] < graph.src_node_dist[i]) {
                    graph.src_node_dist[i] = graph.src_node_dist[u] + graph.graph_matrix[u][i];

                    if (u > 0) { // save parent of recalculated node
                        graph.parents[i] = u;
                        // shortest_path.push_back(u); // add parent to shortest path
                    }
                }
            }
        }
        graph.visited[u] = true; // mark the current node as visited
        graph.subtract_unvisited(); // decrement the visited nodes count
    }
    // fill the shortest path by ordering parents
    fill_shortest_path();

    // return shortest distance src->dest
    return graph.src_node_dist[dest];
}

// ordering the parent nodes to fill shortest_path node list
void Shortest_Path::fill_shortest_path()
{
    int dest_node = graph.V - 1;
    shortest_path.push_front(dest_node);
    // prepend each parent from dest node up to src (0th element)
    for (int i = dest_node; i > 0;) {
        shortest_path.push_front(graph.parents[i]);
        i = graph.parents[i];
    }
}

// print shortest path from src->dest node by node
void Shortest_Path::print_shortest_path()
{
    // print out src to dest shortest path to the console
    // using newest C++11 standard range based for loop
    cout << shortest_path.front(); // print first node

    list<int>::iterator it = shortest_path.begin();
    ++it;
    // print out all other nodes
    for (; it != shortest_path.end(); ++it)
        cout << " -> " << *it;

    cout << endl;
}