ワーシャル-フロイド法 サンプルプログラム
ワーシャル-フロイド法
(ダイクストラは個別ルートでは早いが、先に全ルート計算しておくなら、
こっちの方法の法が速いこともある)
と、
STLのリストの使い方(ファンクションへのリストの渡し方とか、リストの複製の作り方とか)
などの、便利な技が仕込まれているので貼っておく
/*
g++ -g wf.cpp -o wf
ワーシャル-フロイド法
(ダイクストラは個別ルートでは早いが、先に全ルート計算しておくなら、
こっちの方法の法が速いこともある)
と、
STLのリストの使い方(ファンクションへのリストの渡し方とか、リストの複製の作り方とか)
などの、便利な技が仕込まれているので貼っておく
*/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <list> // list 利用のため
using namespace std;
//int d[100][100]; // d[i][k]：ノードiからノードkへの距離
//int via[100][100]; // d[i][k]の間にある(少くとも1つの)中継ノード
double d[100][100]; // d[i][k]：ノードiからノードkへの距離
int via[100][100]; // d[i][k]の間にある(少くとも1つの)中継ノード
list<int> path[100][100]; // int 型の list を宣言
#if 1
// 中継パスの表示ルーチン(再帰呼出し用)
void printPath1_aux(int begin, int end) {
if (via[begin][end] == begin) {
if (begin != end)
printf("%02d -> ", begin);
return;
}
printPath1_aux(begin, via[begin][end]);
printPath1_aux(via[begin][end], end);
}
#endif
// 中継パスの表示ルーチン(再帰呼出し用)
void printPath1_aux(int begin, int end, list<int>* p) {
if (via[begin][end] == begin) {
if (begin != end){
// printf("%02d -> ", begin);
p->push_back(begin);
}
return;
}
printPath1_aux(begin, via[begin][end], p);
printPath1_aux(via[begin][end], end, p);
}
// 中継パスの表示ルーチン
#if 1
void printPath1(int start, int goal) {
printPath1_aux(start, via[start][goal]);
printPath1_aux(via[start][goal], goal);
printf("%02d\n", goal);
}
#endif
void printPath1(int start, int goal, list<int> *p ) {
printPath1_aux(start, via[start][goal], p);
printPath1_aux(via[start][goal], goal, p);
// printf("%02d\n", goal);
p->push_back(goal);
}
int main(void)
{
// 変数の初期化
for(int i = 0; i < 100; i++){
for(int j = 0; j < 100; j++){
d[i][j] = 999.9; // 距離の初期化(でっかい値を入力しておく(INT_MAXは足し算の時に桁上がりが起こるので使わない)
via[i][j] = i; // ノードiからノードkへの経由値の初期化
}
}
#if 0
// 確認用の表示
printf("\n[STEP1]\n");
for(int i = 0; i < 100; i++){
for(int k = 0; k < 100; k++){
printf("d[%d][%d]):%f\t",i,k,d[i][k]);
printf("via[%d][%d]):%d\n",i,k,via[i][k]);
}
}
#endif
//// ここからは実際の距離を手書き
for(int i = 0; i < 100; i++){
d[i][i] = 0; //// 同じノードへの距離は0になるので、上書き
}
//ノード番号の通番を以下のようにする
// [0][2] → "02", [4][9] → "49", [9][[9] → "99"
// 座標は1ケタ内に留める
for (int y = 0; y < 5; y++){
for (int x = 0; x < 9; x++){
int n_num = x * 10 + y;
// + ( 1, 0)
int x_new = x + 1;
int y_new = y;
if (x_new < 9){
int n_num_next = x_new * 10 + y_new;
d[n_num][n_num_next] = 0.069;
printf("1:d[%02d][%02d]=%f\n",n_num, n_num_next, d[n_num][n_num_next]);
}
// + (-1, 0)
x_new = x - 1;
y_new = y;
if (x_new > -1 ){
int n_num_next = x_new * 10 + y_new;
d[n_num][n_num_next] = 0.069;
printf("2:d[%02d][%02d]=%f\n",n_num, n_num_next, d[n_num][n_num_next]);
}
// + ( 0, 1)
x_new = x;
y_new = y + 1;
if (y_new < 5 ){
int n_num_next = x_new * 10 + y_new;
d[n_num][n_num_next] = 0.069;
printf("3:d[%02d][%02d]=%f\n",n_num, n_num_next, d[n_num][n_num_next]);
}
// + ( 0,-1)
x_new = x;
y_new = y - 1;
if (y_new > -1 ){
int n_num_next = x_new * 10 + y_new;
d[n_num][n_num_next] = 0.069;
printf("4:d[%02d][%02d]=%f\n",n_num, n_num_next, d[n_num][n_num_next]);
}
}
}
// 実験用上書き
d[02][12] = 0.025;
d[12][22] = 0.025;
d[22][32] = 0.025;
d[32][42] = 0.025;
d[42][52] = 0.025;
d[52][62] = 0.025;
d[62][72] = 0.025;
d[72][82] = 0.025;
d[12][02] = 0.025;
d[22][12] = 0.025;
d[32][22] = 0.025;
d[42][32] = 0.025;
d[52][42] = 0.025;
d[62][52] = 0.025;
d[72][62] = 0.025;
d[82][72] = 0.025;
#if 1
// 確認用の表示
printf("\n[STEP2]\n");
for(int i = 0; i < 99; i++){
for(int k = 0; k < 99; k++){
printf("d[%d][%d]):%f\t",i,k,d[i][k]);
printf("via[%d][%d]):%d\n",i,k,via[i][k]);
}
}
#endif
// 経路長計算
for (int k =0; k < 99; k++){
for (int i =0; i < 99; i++){
for(int j = 0; j < 99; j++){
if(d[i][j] > d[i][k] + d[k][j]){
d[i][j] = d[i][k] + d[k][j];
via[i][j] = k; //更新処理
}
}
}
}
#if 0
// 計算結果
printf("\n[STEP3]\n");
for(int i = 0; i < 99; i++){
for(int k = 0; k < 99; k++){
printf("d[%d][%d]):%f\t",i,k,d[i][k]);
printf("via[%d][%d]):%d\n",i,k,via[i][k]);
}
}
#endif
#if 1
// 経路パス表示
printf("\n[Path]\n");
for(int i = 0; i < 99; i++){
for(int k = 0; k < 99; k++){
if (d[i][k] < 99.9){
printf("d[%02d][%02d]:%f ",i,k,d[i][k]);
printPath1(i, k);
printPath1(i, k, &(path[i][k]));
}
}
}
#endif
// イテレータ (反復子) の定義
list<int>::iterator pos;
list<int> l = path[83][04];
// イテレータをずらしながら、全てのデータを取り出す。
for(pos = l.begin(); pos!=l.end(); ++pos){
cout << *pos << "\n";
}
printf("\n");
// https://cpprefjp.github.io/reference/algorithm/copy.html
// back_inserter を使って l2 へ設定。
// back_inserter は要素をコピーするときに l2.push_back() するイテレータを作る関数。
//std::list<int> l2;
list<int> l2;
//std::copy(l.begin(), l.end(), back_inserter(l2));
copy(l.begin(), l.end(), back_inserter(l2));
// l2.erase(v.begin() + 2); // 3番目の要素（9）を削除
l2.erase(l2.begin()); // 先頭の要素を削除
for(pos = l2.begin(); pos!=l2.end(); ++pos){
cout << *pos << "\n";
}
}