Dijkstra's Algorithm

short_path.cpp

#include <list>
#include <cassert>

#include <iostream>


/* use int (>= 0) to indicate vertex */


struct Edge;


typedef std::list<int> Path;
typedef std::list<Edge> BranchList;


const size_t SIZE = 10000;
const char* PROMPT = " > ";


struct Edge {
  int target;
  double weight;
  Edge(int t, double w) {
    target = t;
    weight = w;
  }
};


class ShortPathTree {
private:
  int* parent;
  double* length;
  int size;
  int start_node;
public:
  ShortPathTree(int N, int start, int* parent_arr, double* length_arr) {
    size = N;
    parent = new int[size];
    length = new double[size];
    for(int i=0; i<size; i++) {
      parent[i] = parent_arr[i];
      length[i] = length_arr[i];
    }
    parent[start] = -1; // root of tree
    length[start] = 0.0;
    start_node = start;
  }
  ~ShortPathTree() {
    delete[] parent;
    delete[] length;
  }
  Path get_path(int terminal) const {
    assert(0 <= terminal && terminal < size);
    if(parent[terminal] == -1) {
      if(terminal == start_node) {
	Path path;
	path.push_front(start_node);
	return path;
      } else {
	return Path();
      }
    } else {
      Path path;
      int node = terminal;
      do {
	path.push_front(node);
	node = parent[node];
      } while(node != -1);
      return path;
    }
  }
  double get_length(int terminal) const {
    assert(0 <= terminal && terminal < size);
    return length[terminal];
  }
  int get_start() const {
    return start_node;
  }
};


class Graph {
private:
  BranchList* branch_lists;
  int size;
public:
  Graph(int N) {
    size = N;
    branch_lists = new BranchList[size];
  }
  ~Graph() {
    delete[] branch_lists;
  }
  void add_edge(int from, int to, double weight) {
    assert(0 <= from && from < size);
    assert(0 <= to && to < size);
    branch_lists[from].push_back(Edge(to, weight));
  }
  /* require all weights are positive */
  ShortPathTree get_short_path_tree(int start) const {
    assert(0 <= start && start < size);
    int *parent = new int[size];
    double *length = new double[size];
    bool *in_tree = new bool[size];
    int tree_size = 1;
    int current = start; // the node that newly added
    for(int i=0; i<size; i++) {
      length[i] = 1.0/0.0;
      in_tree[i] = 0;
      parent[i] = -1;
    }
    in_tree[start] = true;
    length[start] = 0;
    while(tree_size < size) {
      BranchList& neighbors = branch_lists[current];
      for(auto I=neighbors.begin(); I!=neighbors.end(); I++) {
	if(!in_tree[I->target]) {
	  if(length[current] + I->weight < length[I->target]) {
	    length[I->target] = length[current] + I->weight;
	    parent[I->target] = current;
	  }
	}
      }
      double min = 1.0/0.0;
      int min_node = -1;
      for(int i=0; i<size; i++) {
	if(!in_tree[i]) {
	  if(length[i] < min) {
	    min = length[i];
	    min_node = i;
	  }
	}
      }
      if(min_node == -1) {
	break;
      }
      in_tree[min_node] = true;
      current = min_node;
      tree_size++;
    }
    return ShortPathTree(size, start, parent, length);
  }
};


int main(int argc, char **argv) {
  Graph distance(SIZE);
  Graph time(SIZE);
  Graph* current_graph = &distance;
  std::string mode_str = "Distance";
  std::cout << mode_str << PROMPT;
  std::string operation;
  while(std::cin >> operation) {
    if(operation == "add") {
      std::cout << "Input [from] [to] [distance] [time]\n";
      int from, to;
      double distance_value, time_value;
      std::cin >> from >> to >> distance_value >> time_value;
      assert(0 <= from && from < SIZE);
      assert(0 <= to && to < SIZE);
      assert(distance_value > 0);
      assert(time_value > 0);
      distance.add_edge(from, to, distance_value);
      time.add_edge(from, to, time_value);
    } else if(operation == "route") {
      std::cout << "Input [from] [to]\n";
      int from, to;
      std::cin >> from >> to;
      ShortPathTree tree = current_graph->get_short_path_tree(from);
      Path path = tree.get_path(to);
      double length = tree.get_length(to);
      std::cout << "Path ";
      for(auto I=path.begin(); I!=path.end(); I++) {
	std::cout << *I << " ";
      }
      std::cout << "\nLength " << length << "\n";      
    } else if(operation == "toggle") {
      if(mode_str == "Distance") {
	current_graph = &time;
	mode_str = "Time";
      } else {
	current_graph = &distance;
	mode_str = "Distance";
      }
    } else if(operation == "exit") {
      break;
    }
    std::cout << mode_str << PROMPT;
  }
}