Calculation of short path for graph

short_path.cpp

// Compile: $ g++ -Wall -std=c++14 short_path.cpp
#include <cassert>  // For standard debugging tool:
                    // assert
#include <cstdint>  // For using fixed width integer types and part of
                    // C numeric limits interface:
                    // std::uint8_t
#include <iomanip>  // For facilities to manipulate output formatting:
                    // std::setw
#include <iostream> // For input and output fundamentals:
                    // std::cout
                    //      endl
#include <random>   // For random number generator
                    // std::random_device
                    //      mt19937
                    //      uniform_real_distribution
#include <string>   // For C++ standard string classes and templates:
                    // std::to_string
#include <vector>   // For using dynamic array
                    // std::vector

// The usage of vector:
//   Although vector here is used to replace array, but it's not passed by
//   reference(pointer) by default. It's essentially a template, so it works
//   like a object. It will be passed by value unless you specify otherwise
//   using the &-operator or *-operator.
//
// void foo(vector<int> bar);         // by value
// void foo(vector<int> &bar);        // by reference (to a modifyable vector)
// void foo(vector<int> const &bar);  // by const-reference
// void foo(const vector<int> &bar);  // by const-reference
//
// The last two is same. The both 'bar' are references to a const vector.

using std::uint8_t;

using std::setw;

using std::cout;
using std::endl;

using std::to_string;

using std::vector;

// Get the max value to represent infinity.
const uint8_t inf = static_cast<uint8_t>(~0);

//   Helper Functions
// ===================================
void PrintGraph(const vector < vector<uint8_t> >& aGraph)
{
  // Make sure the graph is not empty.
  assert(aGraph.size());

  // The max width of one item is 3 because the max value 255 has 3 digits.
  // Column width should be the max width of columns plus one(for space).
  uint8_t w = 4;
  for (uint8_t i = 0 ; i < aGraph.size(); i++) {
    for (uint8_t j = 0 ; j < aGraph[i].size(); j++) {
      cout << setw(w) <<
        ((aGraph[i][j] >= inf) ? "*" : to_string(aGraph[i][j])) << " ";
    }
    cout << endl;
  }
}

std::vector< std::vector<uint8_t> >
GenerateGraph(unsigned int aSize, float aDensity, bool aDirected = true)
{
  assert(aSize);

  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_real_distribution<> dis(0, 1);

  std::vector< std::vector<uint8_t> > graph;
  graph.resize(aSize);
  for (uint8_t i = 0 ; i < aSize ; ++i) {
    graph[i].resize(aSize);
    for (uint8_t j = i ; j < aSize ; ++j) {
      graph[i][j] = (i == j) ? 0 : (dis(gen) < aDensity) ? dis(gen)*10 : inf;
    }
  }

  for (uint8_t i = 1 ; i < aSize ; ++i) {
    for (uint8_t j = 0 ; j < i ; ++j) {
      graph[i][j] = (aDirected) ? (dis(gen) < aDensity) ? dis(gen)*10 : inf :
                                  graph[j][i];
    }
  }

  if (!aDirected) {
    for (uint8_t i = 0 ; i < aSize ; ++i) {
      for (uint8_t j = 0 ; j < aSize ; ++j) {
        assert(graph[i][j] == graph[j][i]);
      }
    }
  }

  return graph;
}

//   Floyd-Warshall
// ===================================
vector < vector<uint8_t> > FloydWarshall(const vector < vector<uint8_t> >& aGraph)
{
  // Make sure the graph is not empty.
  assert(aGraph.size());

  // Copy a graph;
  vector < vector<uint8_t> > graph = aGraph;

  for (uint8_t k = 0 ; k < graph.size() ; k++) {
    for (uint8_t i = 0 ; i < graph.size(); i++) {
      for (uint8_t j = 0 ; j < graph[i].size(); j++) {
        // Do nothing with the unconnected nodes.
        if (graph[i][k] >= inf || graph[k][j] >= inf) {
          continue;
        }
        // If pathViaK < graph[i][k] or pathViaK < graph[k][j],
        // then it means the summation is overflow!
        uint8_t pathViaK = graph[i][k] + graph[k][j];
        assert(pathViaK >= graph[i][k] &&
               pathViaK >= graph[k][j]);
        if (pathViaK < graph[i][j]) {
          graph[i][j] = pathViaK;
        }
      }
    }
  }

  return graph;
}

//   Dijkstra
// ===================================
// Dijkstra calculates the shortest path from one source to multiple destinations.
vector<uint8_t> Dijkstra(const vector < vector<uint8_t> >& aGraph, uint8_t aStart)
{
  // Make sure the graph is not empty.
  assert(aGraph.size());

  // To record the shortest distance from start node to other nodes.
  vector<uint8_t> distance(aGraph.size(), inf);
  distance[aStart] = 0;

  // A set that contains the unvisited nodes from start node.
  vector<uint8_t> unvisited;
  for (uint8_t i = 0 ; i < aGraph.size() ; i++) {
    unvisited.push_back(i);
  }

  while (unvisited.size()) {
    // Find the nearest unvisited node from the start node.
    uint8_t minIndex = 0;
    for (uint8_t j = 0 ; j < unvisited.size() ; j++) {
      if (distance[ unvisited[j] ] < distance[ unvisited[minIndex] ]) {
        minIndex = j;
      }
    }
    uint8_t nearest = unvisited[minIndex];

    // Go to the nearest unvisited node and calculate the distances of all the
    // available path via the chosen node.
    unvisited.erase(unvisited.begin() + minIndex);
    for (uint8_t j = 0 ; j < aGraph.size() ; j++) {
      // Do nothing with the unconnected nodes.
      if (aGraph[nearest][j] >= inf) {
        continue;
      }

      // If distance[nearest] is infinity, then pathViaNearest must be infinity
      // too. distance[j] is infinity at first. If pathViaNearest is also
      // infinity, then there is no need to compare them.
      // This happens when there are some unconnected nodes to start left in
      // unvisited set.
      if (distance[nearest] >= inf) {
        continue;
      }

      // If the path via nearest is smaller than the record from start node to
      // others, than we update the records.
      // (Update distance when start->nearest->others < start->others.)
      uint8_t pathViaNearest = distance[nearest] + aGraph[nearest][j];

      // If pathViaNearest < distance[nearest] or aGraph[nearest][j], it means
      // the summation is overflow!
      assert(pathViaNearest >= distance[nearest] &&
             pathViaNearest >= aGraph[nearest][j]);

      if (pathViaNearest < distance[j]) {
        distance[j] = pathViaNearest;
      }
    }
  }

  // Make sure all nodes have been visited.
  assert(!unvisited.size());

  return distance;
}

// Dijkstra only calculate shortest path from one source to multiple destinations.
// To get the shortest distances of whole graph, we need to use a loop to do it.
vector < vector<uint8_t> > Dijkstra(const vector < vector<uint8_t> >& aGraph)
{
  // The graph record the results.
  vector < vector<uint8_t> > graph;
  graph.resize(aGraph.size());

  // Set the start point to calculate the shortest path.
  for (uint8_t start = 0 ; start < aGraph.size() ; start++) {
    // Append the distance path from "start" to the result.
    graph[start] = Dijkstra(aGraph, start);
  }

  return graph;
}

//   Bellman-Ford
// ===================================
vector<uint8_t> BellmanFord(const vector < vector<uint8_t> >& aGraph, uint8_t aStart)
{
  // Make sure the graph is not empty.
  assert(aGraph.size());

  // To record the shortest distance from start node to other nodes.
  vector<uint8_t> distance(aGraph.size(), inf);
  distance[aStart] = 0;

  // Update the distance (n - 1) times, where n is the number of nodes.
  for (uint8_t i = 0 ; i < aGraph.size() - 1 ; i++) {
    // Go throug all the edges to update the distance.
    for (uint8_t j = 0 ; j < aGraph.size() ; j++) {
      for (uint8_t k = 0 ; k < aGraph.size() ; k++) {
        // No edage between node j and k. Ignore it!
        if (aGraph[j][k] >= inf) {
          continue;
        }

        // If distance[j] is infinity, then pathToKViaJ must be infinity too.
        // distance[k] is infinity at first. If pathToKViaJ is also infinity,
        // then there is no need to compare them.
        if (distance[j] >= inf) {
          continue;
        }

        uint8_t pathToKViaJ = distance[j] + aGraph[j][k];
        // If pathToKViaJ < distance[j] or pathToKViaJ < aGraph[j][k],
        // it means the summation is overflow!
        assert(pathToKViaJ >= distance[j] && pathToKViaJ >= aGraph[j][k]);
        if (pathToKViaJ < distance[k]) {
          distance[k] = pathToKViaJ;
        }
      }
    }
  }

  return distance;
}

vector < vector<uint8_t> > BellmanFord(const vector < vector<uint8_t> >& aGraph)
{
  // The graph record the results.
  vector < vector<uint8_t> > graph;
  graph.resize(aGraph.size());

  // Set the start point to calculate the shortest path.
  for (uint8_t start = 0 ; start < aGraph.size() ; start++) {
    // Append the distance path from "start" to the result.
    graph[start] = BellmanFord(aGraph, start);
  }

  return graph;
}


int main()
{
  // Initialize the path of two nodes in the map.
  // vector < vector<uint8_t> > graph = {
  //   {   0,   2,   6,   4 },
  //   { inf,   0,   3, inf },
  //   {   7, inf,   0,   1 },
  //   {   5, inf,  12,   0 }
  // };
  // vector < vector<uint8_t> > graph = {
  //   {   0,   1,  12, inf, inf, inf },
  //   { inf,   0,   9,   3, inf, inf },
  //   { inf, inf,   0, inf,   5, inf },
  //   { inf, inf,   4,   0,  13,  15 },
  //   { inf, inf, inf, inf,   0,   4 },
  //   { inf, inf, inf, inf, inf,   0 }
  // };
  vector < vector<uint8_t> > graph = GenerateGraph(6, 0.5f);
  // If the distance of two nodes is infinity,
  // then it means they are unconnected.

  // Print the initial path between any two nodes in the map.
  cout << "Initial Distance:" << endl;
  PrintGraph(graph);

  // Print the shortest path calculated by Floyd-Warshall algorithm between
  // any two nodes in the map.
  cout << endl << "Shortest Path by Floyd-Warshall:" << endl;
  vector < vector<uint8_t> > fw = FloydWarshall(graph);
  PrintGraph(fw);

  // Print the shortest path calculated by Dijkstra algorithm between
  // any two nodes in the map.
  cout << endl << "Shortest Path by Dijkstra:" << endl;
  vector < vector<uint8_t> > dij = Dijkstra(graph);
  PrintGraph(dij);

  // Print the shortest path calculated by Bellman-Ford algorithm between
  // any two nodes in the map.
  cout << endl << "Shortest Path by Bellman-Ford:" << endl;
  vector < vector<uint8_t> > bf = BellmanFord(graph);
  PrintGraph(bf);

  // The three results should be same.
  assert(fw == dij && dij == bf);

  return 0;
}