C 言語の最短パス アルゴリズム (Floyd アルゴリズム)
上位カテゴリ : [C 言語] C 言語目次
1. さまざまな距離の概念
a. GitHub
1. (参考) 各種距離概念
⑴ 距離関数: 距離を定義します
⑵ タイプ 1: L1 距離
⑶ タイプ 2: L2 距離: 三平方の定理を使用したユークリッド距離 (標準)
⑷ タイプ 3: p ノルム
⑸ タイプ 4: 内積
⑹ タイプ 5: リンケージメトリック: クラスター間の距離を定義します
⑺ タイプ 6: KL 距離 %80%20%EC%97%94%ED%8A%B8%EB%A1%9C%ED%94%BC,-(相対%20エントロピー%2C)(カルバック・ライブラー発散)
⑻ タイプ 7: ハミング距離: データ点ごとにバイナリ値を指定して、データ点間の距離を測定します。
⑼ タイプ 8: マハラノビス距離: データの分布を測定します。
2\。 C言語で実装された最短パスアルゴリズム
⑴ 問題の状況: たとえば、0 から 5 へのパスには 6 のコストが必要です。つまり、6 の距離を移動する必要があります。
⑵ C言語コード
「」c
#include
int W[頂点数][頂点数] = { // W[i][j] は i から j までの直接距離を表し、値が大きいほど直接移動できないことを示します {0, 遠距離, 2, 3, 3, 6}, {遠距離, 0, 遠距離, 4, 2, 遠距離}, {10, 2, 0, 5, 1, Far_Distance}, {遠い距離, 遠い距離, 4, 0, 遠い距離, 2}, {5, 9, 遠距離, 4, 0, 3}, {遠い距離, 遠い距離, 遠い距離, 4, 遠い距離, 0}, };
int D[頂点数][頂点数]; // D[i][j] には i から j までの最小距離が格納されます int P[頂点数][頂点数]; // P[i][j] は、i から j まで通過した最高次数の頂点を格納します
void フロイド(){ int i、j、k; for(i=0; i < Count_Vertice; i++) // 配列を初期化します for(j=0; j < Count_Vertice; j++){ P[i][j] = -1; D[i][j] = W[i][j]; } for(k=0; k < Count_Vertice; k++) for(i=0; i < Count_Vertice; i++) for(j=0; j < Count_Vertice; j++) if(D[i][j] > D[i][k] + D[k][j]){ /* kを経由することでD[i][j]が短くなった場合 */ D[i][j] = D[i][k] + D[k][j]; P[i][j] = k; } }
void Print_Path(int a, int b){ // Print_Path[i][j] の i と j は印刷されないことに注意してください if(P[a][b] != -1) { // P[a][b] = -1 “= 最短距離は a から b までの直線です Print_Path(a, P[a][b]); printf(“%d “, P[a][b]); Print_Path(P[a][b], b); } }
int main(int argc, char *argv[]){ フロイド（）; int a、b; printf(“出発点と目的地を入力してください。(0 ~ %d)\n”, Count_Vertice - 1); scanf(“%d %d”, &a, &b); printf(“最短距離: %d\n”, D[a][b]); printf(“最短パス: “); printf(“%d “, a); Print_Path(a, b); if(D[a][b] != 0) printf(“%d”, b); // D[a][b] = 0
「= a = b 0を返します。 } 「」
入力: 2013 年 12 月 13 日 22:55