dijkstra-shortest-path-algorithm/main.cpp

#include <iostream>
#include <cstdlib>
#include <time.h>
#include "graph.h"
#include "shortest_path.h"

using namespace std;

// get average path from 0 to each subsequent node
float average_path(Shortest_Path s_path) {
    float sum = 0;
    int count = 0;
    float avg = 0.0;
    float s_path_val = 0.0;

    for (int i = 1; i < s_path.get_graph().V; ++i) {
        s_path_val = s_path.calculate_path(0, i);
        // if shortest from 0 to node exists
        if (s_path_val != INF) {
            sum += s_path_val; // add value to sum
            ++count; // increase count of additions
        }
    }

    avg = sum / count;

    return avg;
}

void print_graph_path_stats(Shortest_Path s_path, int src, int dest)
{
    // filter out false src - dest
    int graph_size = s_path.get_graph().V;

    if (src < 0 || src >= graph_size || dest < 0 || dest >= graph_size) {
        cout << "Coordinates are outside the graph range." << endl;
        return;
    }

    cout << "Graph with "
         << s_path.get_graph().get_density() * 100 << "% density \n" << endl;
    s_path.get_graph().print_graph();



    float min_node_dist = s_path.calculate_path(src, dest);

    if (min_node_dist == INF || min_node_dist == 0) {
        cout << "No path exists between nodes "
             << src << " and " << dest << "." << endl;
    } else {
        cout << "\nAverage shortest path for this graph: "
             << average_path(s_path) << endl;
        cout << "------------------------------------------" << endl;
        cout << "Minimal (" << src << " -> " << dest << ") node distance: "
             << s_path.calculate_path(src, dest) << endl;
        cout << "Shortest path ("
             << src << " -> " << dest << ") node sequence: " << endl;
        s_path.print_shortest_path();
        cout << "------------------------------------------\n" << endl;
    }
}

int main()
{
    // initialize seed for random generation
    srand(static_cast<unsigned>(time(0)));

    // create two graphs with 50 nodes and randomly generated
    // edges in range 1.0 to 10.0, with densities 20% and 40%
    Graph g1(50, 10.0, 0.2);
    Graph g2(50, 10.0, 0.4);

    // assign graphs to paths
    Shortest_Path s_path1(g1);
    Shortest_Path s_path2(g2);

    // show following statistics about each graph
    // (average shortest path, min 0-49 node distance, shortest path node sequence)

    cout << "*** DIJSKTRA ALGORITHM ***\n" << endl;
    print_graph_path_stats(s_path1, 0, 49);
    print_graph_path_stats(s_path2, 0, 49);

    return 0;
}