数据结构（C）一分钟看懂最短路径的Dijkstra算法和Floyd算法

1.最短路径：有向图中给定两个顶点间权值和最小的路径，如果从A不能到达B,则A到B的路径长度为无穷大。
2.算法：①Dijkstra算法——从某一源点到其余各顶点的最短路径，O（n^2）
②Floyd算法——每一对顶点之间的最短路径,O（n^3）

Dijkstra（从已知最短路径扩大到目标最短路径）

算法流程图

文字描述：
1.起点v0和其余每个顶点的路径(数组D)中取最小值，这这个最小值就是v0和该点的最短路径长度

2.将这个点假如是V1并入v0的集合S，然后由v0走到v1在走到其余每个顶点这样方式得到路径长度，去更新v0到其余各点的最短路径长度(数组D)

1’.更新完毕后，再D中处S中的点以外，找最小值，这个值，就是这个最小值就是v0和该点确定的最短路径长度

2’并入，以最新找到的最短路径开始更新

…
（重复这两个步骤）直到S（已找到最短路径的点的集合）中有源点和终点
例子

PS.行表头表示进行最短路径的扩充的次数，6个顶点最多扩充5次 ；列表头表示源点到其余各个顶点的更新后的路径长度；红色，表示发生了更新；紫色表示从源点到该点的一条最短路径。
代码（提供思路）

#include<stdio.h>
#include<stdlib.h>
#define max 11000000000
int a[1000][1000];
int d[1000];//d表示某特定边距离
int p[1000];//p表示永久边距离
int i, j, k;
int m;//m代表边数
int n;//n代表点数
int main()
{
    scanf("%d%d",&n,&m);
    int    min1;
    int    x,y,z;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=z;
        a[y][x]=z;
    }
    for( i=1; i<=n; i++)
        d[i]=max1;
        d[1]=0;
    for(i=1;i<=n;i++)
    {
        min1 = max1;
        for(j=1;j<=n;j++)
            if(!p[j]&&d[j]<min1)
            {
                min1=d[j];
                k=j;
            }
        p[k]=d[k];
        for(j=1;j<=n;j++)
            if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
                d[j]=d[k]+a[k][j];
    }
    for(i=1;i<n;i++)
        printf("%d->",p[i]);
    printf("%d\n",p[n]);
    return 0;
}

Floyd算法（动态规划）

a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。（当然w和u之间可以有其他节点）

…
当所有的节点都作为w试探过后，最后得到的路径便是最短路径
例子：

行表头如D(0)表示通过0号顶点经行试探，-1表示初始值；下方的表表示路径
代码（提供思路）

#include<stdio.h>
#include<stdlib.h>
#define max 1000000000
 
int d[1000][1000],path[1000][1000];
int main()
{
    int i,j,k,m,n;
    int x,y,z;
    scanf("%d%d",&n,&m);
     
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            d[i][j]=max;
            path[i][j]=j;
    }
     
    for(i=1;i<=m;i++) {
            scanf("%d%d%d",&x,&y,&z);
            d[x][y]=z;
            d[y][x]=z;
    }
     
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++) {
                if(d[i][k]+d[k][j]<d[i][j]) {
                    d[i][j]=d[i][k]+d[k][j];
                    path[i][j]=path[i][k];
                }
            }
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
          if (i!=j) printf("%d->%d:%d\n",i,j,d[i][j]);
    int f, en;
    scanf("%d%d",&f,&en);
    while (f!=en) {
        printf("%d->",f);
        f=path[f][en];
    }
    printf("%d\n",en);
    return 0;
}