AtCoder で公開されている「典型アルゴリズム問題集」のE問題をC++で解いてみました。
E問題 全点対最短経路問題
問題はリンク先をご覧ください。
グラフのすべての点から、他のすべての点への最小移動距離を求めます。
解答案
ダイクストラ法（Dijkstra’s algorithm）では、ある1点から、他のすべての点への最小移動距離を求めました。この記事で紹介するワーシャル–フロイド（Warshall-Floyd）法では、すべての点から自分自身を含むすべての点への最小移動距離を $O(N^3)$ の計算量で求めることができます。
詳しくは、この記事でアルゴリズムを紹介しています。
C++ プログラム例
ほぼワーシャル–フロイド法の定番コードとなっています。ポイントとなるコードの背景色を変更しておきます。
以下が、C＋＋プログラムとなります。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
int main()
{
int n, m;
cin >> n >> m;
vector<vector<ll>> dist(n, vector<ll>(n, INF));
for (int i = 0; i < n; ++i) {
dist[i][i] = 0;
}
for (int i = 0; i < m; ++i) {
int u, v;
ll c;
cin >> u >> v >> c;
dist[u][v] = c;
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if ((dist[i][k] < INF)&&(dist[k][j] < INF)) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
ll result = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
result += dist[i][j];
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
このアルゴリズムもすでに記事で紹介している内容ですが紹介しました。繰り返し紹介することによって、理解が深まればと考えています。
この問題集は、わたくしには、ちょうど良い難易度でした。引き続き解答案を紹介していきます。
