ベルマンフォードアルゴリズムをC++で

アルゴリズムの経過をアニメーションgifにするために書いたはいいものの、アルゴリズムとは関係ないコードが増えてしまったので、C++で書き直してみた。以下コード。

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <math.h>

using namespace std;

class DirectedGraph {
public:
  DirectedGraph() {
  };
  virtual ~DirectedGraph() {
  };
  void add_node(string v) {
	if (find(nodes.begin(), nodes.end(), v) == nodes.end())  
	  nodes.push_back(v);
  };
  void add_edge(string u, string v, double w){
	add_node(u);
	add_node(v);
	map<string, string> edge;
	edge.insert(pair<string, string>(u, v));
	weights.insert(pair<map<string, string>, double>(edge, w));	
  };
  bool bellman_ford(string s){
	// initialization
	map<string, double> d;
	map<string, string> pi;
	for (vector<string>::iterator it = nodes.begin(); it != nodes.end(); ++it) {
	  d[*it] = HUGE_VAL;
	  pi[*it] = "\0";
	}
	d[s] = 0.0;
	for (unsigned int i = 0; i < nodes.size() - 1; ++i) {
	  for (map<map<string, string>, double>::iterator it = weights.begin(); it != weights.end(); ++it) {
		string u = (*it).first.begin()->first;
		string v = (*it).first.begin()->second;
		double w = (*it).second;
		// relax
		if (d[v] > d[u] + w) {
		  d[v] = d[u] + w;
		  pi[v] = u;
		}
	  }
	}
	for (map<map<string, string>, double>::iterator it = weights.begin(); it != weights.end(); ++it) {
	  string u = (*it).first.begin()->first;
	  string v = (*it).first.begin()->second;
	  double w = (*it).second;
	  if (d[v] > d[u] + w) 
		return false;
	}
	// print result
	for (vector<string>::iterator it = nodes.begin(); it != nodes.end(); ++it) {
	  vector<string> result;
	  string v = *it;
	  while(v != s) {
		result.push_back(v);
		v = pi[v];
	  }
	  reverse(result.begin(), result.end());
	  result.insert(result.begin(), s);
	  unsigned int i = 0;
	  for (vector<string>::iterator node_itr = result.begin(); node_itr != result.end(); ++node_itr) {
		if (i < result.size() - 1) {
		  cout << *node_itr << " -> ";
		} else {
		  cout << *node_itr;
		}
		i++;
	  }
	  cout << " (" << d[*it] << ")" << endl;
	}
	return true;
  };
private:
  vector<string> nodes;
  map<map<string, string>, double> weights;
};

int main (int argc, char **argv) {
  DirectedGraph g;
  g.add_edge("a", "b", 6.0);
  g.add_edge("a", "c", 7.0);
  g.add_edge("b", "d", 5);
  g.add_edge("b", "e", -4.0);
  g.add_edge("b", "c", 8.0);
  g.add_edge("c", "d", -3.0);
  g.add_edge("c", "e", 9.0);
  g.add_edge("d", "b", -2);
  g.add_edge("e", "d", 7.0);
  g.add_edge("e", "a", 2.0);
  g.bellman_ford("a");
  return 0;
}

実行結果

/Users/syou6162/discrete_optimization_theory% ./a.out                   
a (0)
a -> c -> d -> b (2)
a -> c (7)
a -> c -> d (4)
a -> c -> d -> b -> e (-2)