ChunMinChang
5/4/2017 - 6:26 AM
Shortest Path
Shortest Path
#include "ShortestPath.h"
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <math.h>
#include <random>
#include <string>
#include <vector>
// The digits of the distance value;
const unsigned int DIGITS = 1;
void
PrintGraph(const std::vector< std::vector<int> >& aGraph)
{
assert(!aGraph.empty());
unsigned int w = DIGITS + 2;
for (auto& nodes: aGraph) {
for (auto& node: nodes) {
std::cout << std::setw(w) <<
((node == INF) ? "*" : std::to_string(node)) << " ";
}
std::cout << std::endl;
}
}
// std::vector< std::vector<const int> >
std::vector< std::vector<int> >
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);
const unsigned int times = pow(10.0, DIGITS);
std::vector< std::vector<int> > graph;
graph.resize(aSize);
for (unsigned int i = 0 ; i < aSize ; ++i) {
graph[i].resize(aSize);
for (unsigned int j = i ; j < aSize ; ++j) {
graph[i][j] = (i == j) ? 0 : (dis(gen) < aDensity) ? dis(gen) * times : INF;
}
}
for (unsigned int i = 1 ; i < aSize ; ++i) {
for (unsigned int j = 0 ; j < i ; ++j) {
graph[i][j] = (aDirected) ? (dis(gen) < aDensity) ? dis(gen) * times : INF :
graph[j][i];
}
}
if (!aDirected) {
for (unsigned int i = 0 ; i < aSize ; ++i) {
for (unsigned int j = 0 ; j < aSize ; ++j) {
assert(graph[i][j] == graph[j][i]);
}
}
}
return graph;
}
int main()
{
// std::vector< std::vector<int> > 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 }
// };
// std::vector< std::vector<int> > graph = GenerateGraph(6, 0.5f, false);
std::vector< std::vector<int> > graph = GenerateGraph(6, 0.3f);
std::cout << "Graph: " << std::endl;
PrintGraph(graph);
std::cout << std::endl;
std::cout << "Shortest path by Floyd-Warshall: " << std::endl;
std::vector< std::vector<int> > fw = FloydWarshall(graph);
PrintGraph(fw);
std::cout << std::endl;
std::cout << "Shortest path by Dijkstra: " << std::endl;
std::vector< std::vector<int> > dij = Dijkstra(graph);
PrintGraph(dij);
std::cout << std::endl;
std::cout << "Shortest path by Bellman-Ford-Moore: " << std::endl;
std::vector< std::vector<int> > bfm = BellmanFordMoore(graph);
PrintGraph(bfm);
assert(bfm == dij && dij == fw);
return 0;
}CXX=g++
CFLAGS=-Wall -std=c++14
SOURCES=test.cpp\
BellmanFordMoore.cpp\
Dijkstra.cpp\
FloydWarshall.cpp
OBJECTS=$(SOURCES:.cpp=.o)
EXECUTABLE=run_test
all: $(EXECUTABLE)
$(EXECUTABLE): $(OBJECTS)
$(CXX) $(CFLAGS) $(OBJECTS) -o $(EXECUTABLE)
.cpp.o:
$(CXX) -c $(CFLAGS) $< -o $@
clean:
rm $(EXECUTABLE) *.o#if !defined(SHORTEST_PATH_H)
#define SHORTEST_PATH_H
#include <vector>
const int INF = ((unsigned int) ~0) >> 1; // The max value of int.
// Graph:
// To
// +---+---+---+---+- -+---+
// | | 0 | 1 | 2 | ... | N |
// +---+---+---+---+- -+---+
// F | 0 | 0 | . | . | ... | . |
// r +---+---+---+---+- -+---+
// o | 1 | . | 0 | . | ... | . |
// m +---+---+---+---+- -+---+
// | 2 | . | . | 0 | ... | . |
// +---+---+---+---+- -+---+
// | . | ............. | . |
// . ............. .
// | . | ............. | . |
// +---+- -+---+
// | N | ............. | 0 |
// +---+- -+---+
std::vector< std::vector<int> >
Dijkstra(std::vector< std::vector<int> >& aGraph);
std::vector< std::vector<int> >
FloydWarshall(std::vector< std::vector<int> >& aGraph);
std::vector< std::vector<int> >
BellmanFordMoore(std::vector< std::vector<int> >& aGraph);
#endif // SHORTEST_PATH_H#include "ShortestPath.h"
#include <assert.h>
std::vector< std::vector<int> >
FloydWarshall(std::vector< std::vector<int> >& aGraph)
{
assert(!aGraph.empty());
// Copy the graph so we don't change the input one.
std::vector< std::vector<int> > result = aGraph;
for (unsigned int k = 0 ; k < aGraph.size() ; ++k) {
for (unsigned int i = 0 ; i < aGraph.size() ; ++i) {
for (unsigned int j = 0 ; j < aGraph.size() ; ++j) {
if (result[i][k] >= INF || result[k][j] >= INF) {
continue;
}
int pathViaK = result[i][k] + result[k][j];
assert(pathViaK >= result[i][k] && pathViaK >= result[k][j]);
if (pathViaK < result[i][j]) {
result[i][j] = pathViaK;
}
}
}
}
return result;
}
#include "ShortestPath.h"
#include <assert.h>
unsigned int
IndexOfMin(std::vector<unsigned int>& aNodes, std::vector<int>& aDistances)
{
assert(!(aNodes.empty() || aDistances.empty()));
unsigned int index = 0;
for (unsigned int i = 1 ; i < aNodes.size() ; ++i) {
unsigned int node = aNodes[i];
if (aDistances[node] < aDistances[aNodes[index]]) {
index = i;
}
}
return index;
}
std::vector<int>
Dijkstra(std::vector< std::vector<int> >& aGraph, unsigned int aStart)
{
assert(!aGraph.empty());
// To record the shortest distance from start node to other nodes.
std::vector<int> distances(aGraph.size(), INF);
distances[aStart] = 0;
// start node
// v
// +---+---+---+- -+---+- -+---+
// node | 0 | 1 | 2 | ... | k | ... | N |
// +---+---+---+- -+---+- -+---+
// distance | * | * | * | ... | 0 | ... | * |
// +---+---+---+- -+---+- -+---+
// A set that contains the unvisited nodes from start node.
std::vector<unsigned int> unvisit;
for (unsigned int i = 0 ; i < aGraph.size() ; ++i) {
unvisit.push_back(i); // Put all nodes at the first.
}
// start node
// v
// +---+---+---+- -+---+- -+---+
// index | 0 | 1 | 2 | ... | k | ... | N |
// +---+---+---+- -+---+- -+---+
// node | 0 | 1 | 2 | ... | k | ... | N |
// +---+---+---+- -+---+- -+---+
while (!unvisit.empty()) {
// Find the nearest unvisited node from the start node.
unsigned int minIndex = IndexOfMin(unvisit, distances);
unsigned int nearest = unvisit[minIndex];
// Go to the nearest unvisited node and calculate the distances
// of all the available path via the chosen node.
unvisit.erase(unvisit.begin() + minIndex);
for (unsigned int i = 0 ; i < aGraph.size() ; ++i) {
// Skip the unconnected node.
if (distances[nearest] >= INF || aGraph[nearest][i] >= INF) {
continue;
}
// If the path via nearest is shorter than the record from start node to
// others, than we update the records.
int pathViaNearest = distances[nearest] + aGraph[nearest][i];
assert(pathViaNearest >= distances[nearest] &&
pathViaNearest >= aGraph[nearest][i]);
if (pathViaNearest < distances[i]) {
distances[i] = pathViaNearest;
}
}
}
return distances;
}
std::vector< std::vector<int> >
Dijkstra(std::vector< std::vector<int> >& aGraph)
{
std::vector< std::vector<int> > results;
results.resize(aGraph.size());
// Set the start point to calculate the shortest path.
for (unsigned int start = 0 ; start < aGraph.size() ; ++start) {
// Append the distance path from "start" to the result.
results[start] = Dijkstra(aGraph, start);
}
return results;
}#include "ShortestPath.h"
#include <assert.h>
std::vector<int>
BellmanFordMoore(std::vector< std::vector<int> >& aGraph, unsigned int aStart)
{
assert(!aGraph.empty());
// To record the shortest distance from start node to other nodes.
std::vector<int> distances(aGraph.size(), INF);
distances[aStart] = 0;
// start node
// v
// +---+---+---+- -+---+- -+---+
// node | 0 | 1 | 2 | ... | k | ... | N |
// +---+---+---+- -+---+- -+---+
// distance | * | * | * | ... | 0 | ... | * |
// +---+---+---+- -+---+- -+---+
// <-- N - 1 edges -->
// 1 -- 2 -- 3 -- ... -- N
//
// If we have N nodes, then there are at the most (N - 1) edges
// to connect these nodes. Thus, we need to update the distances among nodes
// (N-1) times at the most.
for (unsigned int i = 0 ; i < aGraph.size() - 1 ; ++i) {
// Go throug all the edges to update the distance.
for (unsigned int j = 0 ; j < aGraph.size() ; ++j) {
for (unsigned int k = 0 ; k < aGraph.size() ; ++k) {
// Skip the unconnected node.
if (distances[j] >= INF || aGraph[j][k] >= INF) {
continue;
}
int pathToKViaJ = distances[j] + aGraph[j][k];
assert(pathToKViaJ >= distances[j] && pathToKViaJ >= aGraph[j][k]);
if (pathToKViaJ < distances[k]) {
distances[k] = pathToKViaJ;
}
}
}
}
return distances;
}
std::vector< std::vector<int> >
BellmanFordMoore(std::vector< std::vector<int> >& aGraph)
{
std::vector< std::vector<int> > results;
results.resize(aGraph.size());
// Set the start point to calculate the shortest path.
for (unsigned int start = 0 ; start < aGraph.size() ; ++start) {
// Append the distance path from "start" to the result.
results[start] = BellmanFordMoore(aGraph, start);
}
return results;
}