フロイド-11404

1.概要
質問リンク:https://www.acmicpc.net/problem/11404
2.コード

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define INF 0xFFFFFF
int n, m = 0;
std::vector<std::vector<int>> memo;

void floyd_warshall() {
	for (int i = 1; i <= n; i++) {            
		for (int j = 1; j <= n; j++) {       
			for (int k = 1; k <= n; k++) {    
				if (memo[j][i] != INF && memo[i][k] != INF) {
					memo[j][k] = std::min(memo[j][k], memo[j][i] + memo[i][k]);
				}
			}
		}
	}
}

int main(void) {
	std::cin >> n;
	std::cin >> m;
	for (int i = 0; i < n + 1; i++) {
		std::vector<int> vec;
		for (int j = 0; j < n + 1; j++) {
			vec.push_back(INF);
		}
		memo.push_back(vec);
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		std::cin >> a >> b >> c;
		if (memo[a][b] > c) {
			memo[a][b] = c;
		}
	}

	floyd_warshall();

	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < n + 1; j++) {
			if (i == j || memo[i][j] == INF) {
				printf("0 ");
			}
			else {
				printf("%d ", memo[i][j]);
			}
		}
		printf("\n");
	}

	return 0;
}

3.注記
floyd-wassalアルゴリズムは、すべての頂点に複数のアルゴリズムを適用するアルゴリズムです.時間的複雑さはO(V^3)の効率であり,多出口O(E*logV)と比較した.
アルゴリズム実装部はちょっと特別です.基本的な考え方は「真ん中を通るノード」に焦点を合わせることです.

void floyd_warshall() {
	for (int i = 1; i <= n; i++) {            
		for (int j = 1; j <= n; j++) {       
			for (int k = 1; k <= n; k++) {    
				if (memo[j][i] != INF && memo[i][k] != INF) {
					memo[j][k] = std::min(memo[j][k], memo[j][i] + memo[i][k]);
				}
			}
		}
	}
}

このコードでは,i番インデックスノードが「中間通過ノード」となる.jは起点,kは終点である.したがって,iを中心として,以下の2つを比較する.
(j->k)へのパス
vs
(j->i->k)へのパス
例外は次のとおりです.
1)自分向けの場合(j=k):ループが代入される可能性がある.ただし、出力時にローとカラムインデックスが同じであれば、出力を0にすることで解決できます.
2)出発地と目的地指向経路(j=iまたはk=j):自分への直接の経路は常にINFであるため、min内部ではmemo[j][i]+memo[i][k]が常にmemo[j][k]を選択する.
4.コメント

ソース:https://ansohxxn.github.io/algorithm/floyd/
最短パスアルゴリズムには多くの種類があり,それぞれ異なる用途がある.状況に応じて適切なアルゴリズムを選ぶ練習が必要らしい.