[算法] 找到最短路径的Dijkstra, 弗洛伊德

十二月 29, 2014 nguyenvanquan7826 TT图 139 回复


更新 25/05/2014: 做一些你的意见，所以我写了 1 Dijkstra算法程序的结构和功能的方式也略有修改代码更明亮，更准确的^^.

更新 27/09/2014: 该算法的额外帕斯卡代码在这里: http://ideone.com/c7J0dq

内容
Dijkstra算法
弗洛伊德算法
先进的代码 2 算法

更新 14/06/2014: 仿真算法的Dijkstra

在这篇文章中只是指算法找到最短路径的Dijkstra和Floyd, 一些相关的术语我就不解释或定义, 你发现在书籍或在互联网上.

的单源最短路径问题的问题是要找到两个顶点之间的路径，使得构成该最小路边缘的权重的总和. 或者把它的数学:
对于单连通图, 加权G =(该,和). 找到距离d(该,B) 从给定的顶点至G的顶点和b的任何发现从最短路径到b.

正如文章标题, 我们将学习 2 算法采用邻接矩阵结构来解决(注意，我们考虑图的重量不为负).

具有n个顶点的曲线图的邻接矩阵是一个正方形矩阵G n是行列的数. 摹[在][Ĵ] 从i到顶点Ĵ顶部路径的长度. 考虑到无向图G[在][Ĵ] = G[Ĵ][在]. 从上长度本身 0 (摹[在][在] = 0). 如果之间 2 图i和j的边缘不存在的方式，它ģ[在][Ĵ] =无限 (∞). 但是，计算机的性能，该值被设定为∞ 1 常数是非常大的或基质的总价值 (所述边缘的总长度).

1. Dijkstra算法

关于Dijkstra算法有 2 类型是找到从最短路径 1 来源页首 1 首选目的地，找到的最短路径 1 源顶点到图的左上角, 在这里我就说说的东西 1. (第二类，你可以在网络上找到或者只是改变了行 而 (s[B] == 0) (当前 43 通过代码 1 & 当前 76 通过代码 2) 从循环浏览器 0 n-1个是要找到所有顶点).

– 使用 1 莱恩阵列[] – 只[在] 是从一个顶点的最短距离到顶点我.

– 使用 1 薄板S标记的特殊顶点我 (峰值电流i那时，从一个路径到i是最短).

– 使用数组P[] 显着的路径. P[Ĵ] 如果I = I j是超前的最短路径的峰值.

– 复位顶对没有办法极其宝贵.

– 初始化所有的方式，从亚洲到其他峰在极.

– 从初级到初始化路径= 0.

– 浏览图表V的所有顶点

+ 发现上面我不是S中，从一个路径我是最短纳入S中. 如果你找不到批准峰顶可以去还是任何手段都没有找到前目的地=> 走不了.

+ 如果您发现顶点I J浏览所有顶点不属于S. 如果len[在] + 摹[在][Ĵ] < 只[Ĵ] (其中G[在][Ĵ] 是从顶点i到顶点j中的距离) 然后分配莱恩[Ĵ] =莱恩[在] + 摹[在][Ĵ]; 并标明路径P[Ĵ] =我.

注意: 因为在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;
}

升预防油墨

* 每个功能的代码
在代码包含作为功能:
– READDATA 实施读取输入文件.
– Dijkstra算法 实现算法
– 背部 实现返回的字符串是找到办法
– 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;
}

链路冗余

看代码似乎有点长，但阅读长传TEO那么什么时候@@ =)).

2. 弗洛伊德算法

该算法允许我们发现每对顶点之间的最短路径.

如果k的顶点所在的最短路径上，从顶点i到顶点Ĵ，该距离从i到j和从第j到j的最短路径从i到j和从第j至j对应. 因此，我们使用矩阵A为节省每对顶点之间的最短路径长度.
– 最初，我们设置了一个[在,Ĵ] = C[在,Ĵ], 容器是最初的直接路径长度 (不走在上面的所有).
– 然后执行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次迭代, 即阿克[在,Ĵ] là độ dài đường đi ngắn nhất từ i đến j chỉ đi qua các đỉnh thuộc .comment-content 0. 如果[在,Ĵ] 根据下列公式计算: 如果[在,Ĵ] = min .comment-body 9.

– 在迭代过程中，我们必须保存跟踪路径, 即最短路径穿过顶点. 然后我们使用子阵列P[n×n个], 中P[在,Ĵ] 补足如果k最短路径i到与信经过峰. 起初P[在,Ĵ]= 0对所有的i,Ĵ, 因为这时的最短路径是直接路径, 不走在上面的所有.

编码算法:

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 ;
                }
    }
}

如何建立一个完整的程序类似于Dijkstra算法.

先进的代码


这是供选择的代码 1 在 2 算法和输出文件按照该过程的结果在下面的图片 或备份链路

文件input.inp:

8
A 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

菜单控制台
最短路径

输出的Dijkstra
Dijkstra算法

输出弗洛伊德
弗洛伊德