[アルゴリズム] 最短経路ダイクストラを探す, フロイド

12月 29, 2014 nguyenvanquan7826 TTグラフ 139 回答


アップデート 25/05/2014: あなたのコメントのいくつかの操作を行いますので、私はより多くを書いた 1 ところでダイクストラのアルゴリズムプログラムの構造および機能も若干明るく、より正確にするためのコードを改訂^^.

アップデート 27/09/2014: ここでは、アルゴリズムの追加のパスカルコード: http://ideone.com/c7J0dq

コンテンツ
ダイクストラアルゴリズム
フロイドアルゴリズム
のための高度なコード 2 アルゴリズム

アップデート 14/06/2014: シミュレーションアルゴリズムダイクストラ

この記事では唯一の最短経路ダイクストラとフロイドを見つけるアルゴリズムを指し、, 私が説明したり、定義されていませんいくつかの関連用語, あなたは本の中やインターネット上で見つける.

シングルソースの問題は、最短経路問題は、そのような最小の道を構成するエッジの重みの合計は、2つの頂点間のパスを見つけることです. それとも、数学的にそれを置くために:
シングル連結グラフのために, 加重G =(ザ·,と). 距離dを探す(ザ·,B) 与えられた頂点からGの頂点へとAからBへの最短経路を見つけるのすべてのB.

記事のタイトルとして、, 私たちは学習します 2 グラフの隣接行列構造を使用して解決するためのアルゴリズム(我々は、グラフの重みが負でない考える注意).

n個の頂点を持つグラフの隣接行列は正方行列G nは列の行の数である. G[で][J] 私から頂点jのトップへのパスの長さ. 無向グラフGを考える[で][J] = G[J][で]. 上から自身への長さです 0 (G[で][で] = 0). 間の場合、 2 iおよびjは、グラフのエッジは、G方法は存在しない[で][J] =インフィニティ (∞). しかし、コンピュータの性能は、値に設定されている∞ 1 定数が非常に大きいまたは行列の合計値であり、 (エッジの全長).

1. ダイクストラアルゴリズム

ダイクストラのアルゴリズムは有しについて 2 タイプはから最短経路を見つけることである 1 ソースがトップに 1 トップ先からの最短経路を見つける 1 グラフの左上にソース頂点, そしてここで私はものについてお話します 1. (あなたはネット上で見つけるか、単にラインを変更することができます第二種 同時に (S[B] == 0) (現在 43 コー​​ドによる 1 & 現在 76 コー​​ドによる 2) ループブラウザから 0 n-1のすべての頂点を見つけるために起こっている).

– 使用 1 レン·アレイ[] – のみ[で] 私を頂点する頂点までの最短距離である.

– 使用 1 特別な頂点IマーキングプレートS (ピーク電流I当時から私へのパスが最短).

– アレイPを使用して[] マークされたパス. P[J] I = I jは、先に最短経路のピークである場合.

– トップペアは決してないための非常に貴重なリセット.

– 極めてにおける他のピークにアジアからのすべての方法を初期化します.

– =プライマリからパスを初期化する 0.

– グラフVのすべての頂点を見る

+ から私へのパスは、Sに含める最短であることを私はしないSでトップの検索. あなたはまだ行くことができピークの頂点を承認したあらゆる手段を見つけることができない場合=トップ先を見つけていない> 歩くことができませんでした.

+ あなたが頂点を見つけた場合、私がjではないS内にすべての頂点を閲覧する. レンの場合[で] + G[で][J] < のみ[J] (ここで、G[で][J] 私はjは頂点に頂点からの距離である) その後レンを割り当てる[J] =レン[で] + G[で][J]; とマークされたパスP[J] = I.

注意: Cであるため, 配列の開始 0. ピークを計算するとき、したがって、意志上から 0 上部n-1の. しかし、それは上から表示するように残っている 1 Nとトップとトップエンドinput.inpファイルにから計算されます 1 nに. 私たちは、計算や旅行先端の先端を削減する必要がある前に、そのためのコード 1 ユニット. 道路のピークを大きくする必要が検索する際の計算結果、完了後 1 適切に表示するためのユニット (例えば、我々はトップからパスを計算したい 4 トップへ 8, トップ 4 位置に対応する 3 配列内の, トップ 8 対応する位置 7 私たちは削減する必要がある 4 ダウン 3, 8 ダウン 7 計算する. あなたが道を見つけたら, と仮定して 3 -> 5 -> 4 -> 7 ような場所にある必要があります 4 -> 6 -> 5 -> 8).

当社は、以下のチャートに従って練習を行くよ 2 コー​​ドは右でやってメインコンテンツに従っている:

最短経路を見つけるためのアルゴリズム

ファイル input.inp: 最初の行は、 8 ポイント, 離れてポイントから 4 ポイントへ 8. マトリックス8×8 下のグラフの隣接行列である.

8 4 8
0 3 5 2 0 0 0 0
3 0 1 0 7 0 0 0
5 1 0 4 0 1 0 0
2 0 4 0 0 3 6 0
0 7 0 0 0 2 0 3
0 0 1 3 2 0 4 6
0 0 0 6 0 4 0 5
0 0 0 0 3 6 5 0

* メイン内のコード
このコードは、修正されたから、いくつかのバグを修正した。 コー​​ド日前 (または リンクの冗長性).

#include <stdio.h>
#include <stdlib.h>
#define INP "input.inp"
#define OUT "output.out"
 
int main() {
    FILE *fi = fopen(INP, "r");
    FILE *fo = fopen(OUT, "w");
    int n, a, b, i, sum = 0;
 
    // nhap du lieu tu file input
    fscanf(fi, "%d%d%d", &n, &a, &b);
    int G[n][n];
    int S[n], Len[n], P[n];
 
    // nhap ma tran va tinh gia tri vo cung (sum)
    for (i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            fscanf(fi, "%d", &G[i][j]);
            sum += G[i][j];
        }
    // dat vo cung cho tat ca cap canh khong noi voi nhau
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && G[i][j] == 0)
                G[i][j] = sum;
        }
    }
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    for (int i = 0; i < n; i++) {
        Len[i] = sum;                   // khoi tao do dai tu a toi moi dinh la vo cung
        S[i] = 0;                       // danh sach cac diem da xet
        P[i] = a;                       // dat diem bat dau cua moi diem la a
    }
 
    Len[a] = 0;                         // dat do dai tu a -> a la 0
 
    // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for:
    //for (int k = 0; k < n; k++)
    while (S[b] == 0) {                 // trong khi diem cuoi chua duoc xet
        for (i = 0; i < n; i++)          // tim 1 vi tri ma khong phai la vo cung
            if (!S[i] && Len[i] < sum)
                break;
 
        // i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat
        if (i >= n) {
            printf("done dijkstra\n");
            break;
        }
 
        for (int j = 0; j < n; j++) {    // tim diem co vi tri ma do dai la min
            if (!S[j] && Len[i] > Len[j]) {
                i = j;
            }
        }
 
        S[i] = 1;                       // cho i vao danh sach xet roi
 
        for (int j = 0; j < n; j++) {    // tinh lai do dai cua cac diem chua xet
            if (!S[j] && Len[i] + G[i][j] < Len[j]) {
                Len[j] = Len[i] + G[i][j];      // thay doi len
                P[j] = i;                       // danh dau diem truoc no
            }
        }
    }
 
    printf("done dijkstra\n");
 
    /* Do ta dang tinh toan tu dinh 0 nen
     muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */
 
    printf("start find path\n");
 
    if (Len[b] > 0 && Len[b] < sum) {
        fprintf(fo, "Length of %d to %d is %d\n", a + 1, b + 1, Len[b]);
 
        // truy vet
        while (i != a) {
            fprintf(fo, "%d <-- ", i + 1);
            i = P[i];
        }
        fprintf(fo, "%d", a + 1);
    } else {
        fprintf(fo, "khong co duong di tu %d den %d\n", a + 1, b + 1);
    }
 
    printf("done find path\n");
 
    fclose(fi);
    fclose(fo);
 
    printf("done - open file output to see result\n");
    return 0;
}

L予防インク

* 各関数のコード
コー​​ド内の関数を含むように:
– readDataメソッド 実装は、入力ファイルを読み取り.
– ダイクストラ アルゴリズムの実装
– バック 実装は、文字列が見つけるための方法です返す
– outResult 出力ファイルの実施結果

#include <stdio.h>
#include <stdlib.h>
#include <cstring>
 
#define INP "input.inp"
#define OUT "output.out"
 
// read data in file input
int readData(int ***G, int *n, int *a, int *b) {
    FILE *fi = fopen(INP, "r");
    if (fi == NULL) {
        printf("file input not found!\n");
        return 0;
    }
    printf("start read file\n");
 
    fscanf(fi, "%d %d %d", n, a, b);
 
    *G = (int **) malloc((*n) * sizeof(int));
    for (int i = 0; i < *n; i++) {
        (*G)[i] = (int *) malloc((*n) * sizeof(int));
        for (int j = 0; j < *n; j++) {
            int x;
            fscanf(fi, "%d", &x);
            (*G)[i][j] = x;
        }
    }
 
    fclose(fi);
    printf("done read file\n");
    return 1;
}
 
// thuat toan dijkstra
int dijkstra(int **G, int n, int a, int b, int P[]) {
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    printf("start dijkstra\n");
 
    int* Len = (int *) malloc(n * sizeof(int));
    int* S = (int *) malloc(n * sizeof(int));
 
    int sum = 0;            // gia tri vo cung
 
    // tinh gia tri vo cung (sum)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum += G[i][j];
        }
    }
 
    // dat vo cung cho tat ca cap canh khong noi voi nhau
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && G[i][j] == 0)
                G[i][j] = sum;
        }
    }
 
    for (int i = 0; i < n; i++) {
        Len[i] = sum;       // khoi tao do dai tu a toi moi dinh la vo cung
        S[i] = 0;           // danh sach cac diem da xet
        P[i] = a;           // dat diem bat dau cua moi diem la a
    }
 
    Len[a] = 0;             // dat do dai tu a -> a la 0
 
    int i;
 
    // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for:
    //for (int k = 0; k < n; k++)
    while (S[b] == 0) {                 // trong khi diem cuoi chua duoc xet
        for (i = 0; i < n; i++)          // tim 1 vi tri ma khong phai la vo cung
            if (!S[i] && Len[i] < sum)
                break;
 
        // i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat
        if (i >= n) {
            printf("done dijkstra\n");
            return 0;
        }
 
        for (int j = 0; j < n; j++) {    // tim diem co vi tri ma do dai la min
            if (!S[j] && Len[i] > Len[j])
                i = j;
        }
 
        S[i] = 1;                       // cho i vao danh sach xet roi
 
        for (int j = 0; j < n; j++) {    // tinh lai do dai cua cac diem chua xet
            if (!S[j] && Len[i] + G[i][j] < Len[j]) {
                Len[j] = Len[i] + G[i][j];      // thay doi len
                P[j] = i;                       // danh dau diem truoc no
            }
        }
    }
    printf("done dijkstra\n");
    return Len[b];
}
 
//  truy vet duong di
void back(int a, int b, int *P, int n, char *path) {
 
    //char *path = (char *) malloc((n * 10) * sizeof(char));
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    printf("start find path\n");
 
    int i = b;
    int point[n];   // danh sach cac dinh cua duong di
    int count = 0;
 
    /* Do ta dang tinh toan tu dinh 0 nen
     muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */
 
    point[count++] = i + 1;
    while (i != a) {
        i = P[i];
        point[count++] = i + 1;
    }
 
    strcpy(path, "");
    char temp[10];
    for (i = count - 1; i >= 0; i--) {
        sprintf(temp, "%d", point[i]);
        strcat(path, temp);
 
        if (i > 0) {
            sprintf(temp, " --> ");
            strcat(path, temp);
        }
    }
 
    printf("done find path\n");
}
 
void outResult(int len, char* path) {
    FILE *fo = fopen(OUT, "w");
 
    if (len > 0) {
        fprintf(fo, "\nLength of %c to %c is %d\n", path[0],
                path[strlen(path) - 1], len);
    }
 
    fprintf(fo, "path: %s\n", path);
 
    fclose(fo);
}
 
int main() {
    int **G, n, a, b, len;
 
    if (readData(&G, &n, &a, &b) == 0) {
        return 0;
    }
 
    char *path = (char *) malloc((10 * n) * sizeof(char));
    int P[n];
 
    len = dijkstra(G, n, a, b, P);
 
    if (len > 0) {
        back(a, b, P, n, path);
        outResult(len, path);
    } else {
        char *path = (char *) malloc((n * 10) * sizeof(char));
        sprintf(path, "khong co duong di tu %d den %d\n", a, b);
        outResult(len, path);
    }
 
    printf("done - open file output to see result\n");
    return 0;
}

リンクの冗長性

探しているコードは少し長いようだが、その後、テオロングボールを読み込むときに行います@@ =)).

2. フロイドアルゴリズム

このアルゴリズムは、頂点のすべてのペア間の最短経路を見つけることが私たちを可能にする.

k個の頂点が、私はJを頂点に、頂点からの最短経路上にある場合は、私からjへとjからjへの距離は、私からjへとjからJ対応への最短経路である. そこで我々は、頂点のすべての対の間の最短経路の長さを保存するために、行列Aを使用して.
– 当初、我々はセット[で,J] = C[で,J], 最初はダイレクトパスの長さであるコンテナ (すべてでトップの上に行かない).
– そして、n個の反復を実行する, 最初の反復kの後, ma trận A sẽ chứa độ dài đường đi ngắn nhất giữa mọi cặp đỉnh chỉ đi qua các đỉnh thuộc tập .comment-content 1. このような, n個の反復の後、我々は行列Aはグラフの頂点のすべてのペア間の最短経路の長さが含まれ得る.

– Akは後で反復k行列表記である, すなわちAkは[で,J] là độ dài đường đi ngắn nhất từ i đến j chỉ đi qua các đỉnh thuộc .comment-content 0. もし[で,J] 以下の式に従って計算: もし[で,J] = min .comment-body 9.

– 反復プロセスでは、トレースパスを保存する必要が, すなわち最短経路は、頂点を通過する. その後、我々は、サブアレイPを使用[n×nの], そのPで[で,J] J kにIからK最短経路がピークを通過する場合、最大トップ. 当初はP[で,J]= 0すべてのiについて,J, その後最短経路は、ダイレクトパスであるため、, すべてでトップの上に行かない.

コー​​ドアルゴリズム:

void Floyd (int a, int b)
{
    int max = tongthiethai();
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        {
            if (G[i][j])
                A[i][j] = G[i][j];
            else A[i][j] = max;
            P[i][j] = -1;
        }

    for (int k=0; k<n; k++)   // lap n lan
    {
        for (int i=0; i<n; i++)   // thay doi do dai duong di cua cac dinh
            for (int j=0; j<n; j++)
                if (A[i][j] > A[i][k] + A[k][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    P[i][j] = k ;
                }
    }
}

どのように完全なプログラムを構築することはダイクストラのアルゴリズムに似ている.

上級コード


これは選択のためのコードです 1 で 2 下の写真の結果としてプロセスに従い、アルゴリズムや出力ファイル またはバックアップリンク

ファイルinput.inp:

8
B C D E F G H
0 3 5 2 0 0 0 0
3 0 1 0 7 0 0 0
5 1 0 4 0 1 0 0
2 0 4 0 0 3 6 0
0 7 0 0 0 2 0 3
0 0 1 3 2 0 4 6
0 0 0 6 0 4 0 5
0 0 0 0 3 6 5 0

メニューコンソール
最短経路

出力ダイクストラ
ダイクストラ

出力フロイド
フロイド