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

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

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

using namespace std;

class DirectedGraph {
public:
DirectedGraph() {
};
virtual ~DirectedGraph() {
};
if (find(nodes.begin(), nodes.end(), v) == nodes.end())
nodes.push_back(v);
};
void add_edge(string u, string v, double w){
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.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)
```