使用迪杰斯特拉算法或者弗洛伊德算法求图中顶点间的最短路径 (图的邻接矩阵)解释

迪杰斯特拉算法和弗洛伊德算法都是用于求解图中顶点间的最短路径的经典算法。

迪杰斯特拉算法适用于解决单源最短路径问题，即从一个顶点出发，求解该顶点到图中其他顶点的最短路径。算法的基本思想是通过逐步扩展已经找到最短路径的顶点集合，以逐步确定其他顶点的最短路径。具体步骤如下：

1. 初始化距离数组，将源顶点到其他顶点的距离初始化为无穷大，源顶点到自身的距离初始化为0。
2. 选取距离源顶点最近的顶点作为当前顶点，标记该顶点已访问。
3. 更新当前顶点的邻居顶点的距离，如果经过当前顶点到达邻居顶点的距离小于已知的最短距离，则更新最短距离。
4. 重复步骤2和3，直到所有顶点都被访问过或者最短路径已经确定。
5. 最终得到源顶点到所有其他顶点的最短路径。

弗洛伊德算法适用于解决多源最短路径问题，即求解图中任意两个顶点之间的最短路径。算法的基本思想是通过动态规划的方式，逐步更新每对顶点之间的最短路径。具体步骤如下：

1. 初始化距离矩阵，将两个顶点之间的距离初始化为边的权重，如果两个顶点之间没有直接的边相连，则距离为无穷大。
2. 通过动态规划的方式，逐步更新距离矩阵。对于矩阵中的每个元素，尝试经过第k个顶点来更新两个顶点之间的最短路径，如果经过第k个顶点的路径比之前已知的最短路径更短，则更新最短路径。
3. 重复步骤2，直到所有顶点之间的最短路径都被更新。
4. 最终得到任意两个顶点之间的最短路径。

这两个算法在求解图中顶点间最短路径问题上有各自的特点和适用范围，根据具体情况选择合适的算法来解决问题。

相关问题

用c语言实现以下功能：用邻接矩阵创建无向网，并用佛洛伊德算法求任一对顶点间的最短路径及路径长度并输出，用迪杰斯特拉算法求出某一顶点到到其他各顶点间的最短路径及路径长度并输出

以下是用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20
#define INFINITY 65535

typedef struct {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vertices[MAX_VERTEX_NUM]; // 存放顶点信息
    int vexnum, arcnum; // 顶点数和边数
} MGraph;

// 创建无向网
void CreateMGraph(MGraph *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息：\n");
    for (i = 0; i < G->vexnum; ++i) {
        scanf("%d", &G->vertices[i]);
    }
    for (i = 0; i < G->vexnum; ++i) {
        for (j = 0; j < G->vexnum; ++j) {
            G->arcs[i][j] = INFINITY; // 初始化邻接矩阵
        }
    }
    printf("请输入边的信息：\n");
    for (k = 0; k < G->arcnum; ++k) {
        scanf("%d%d%d", &i, &j, &w);
        G->arcs[i][j] = w;
        G->arcs[j][i] = w; // 无向图，对称存储
    }
}

// Floyd算法求任一对顶点间的最短路径及路径长度
void Floyd(MGraph *G, int path[][MAX_VERTEX_NUM], int dist[][MAX_VERTEX_NUM]) {
    int i, j, k;
    for (i = 0; i < G->vexnum; ++i) {
        for (j = 0; j < G->vexnum; ++j) {
            dist[i][j] = G->arcs[i][j];
            path[i][j] = -1;
        }
    }
    for (k = 0; k < G->vexnum; ++k) {
        for (i = 0; i < G->vexnum; ++i) {
            for (j = 0; j < G->vexnum; ++j) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

// 迪杰斯特拉算法求某一顶点到其他各顶点间的最短路径及路径长度
void Dijkstra(MGraph *G, int v, int path[], int dist[]) {
    int i, j, min, u;
    int S[MAX_VERTEX_NUM];
    for (i = 0; i < G->vexnum; ++i) {
        dist[i] = G->arcs[v][i];
        S[i] = 0;
        if (G->arcs[v][i] < INFINITY) {
            path[i] = v;
        } else {
            path[i] = -1;
        }
    }
    dist[v] = 0;
    S[v] = 1;
    for (i = 1; i < G->vexnum; ++i) {
        min = INFINITY;
        for (j = 0; j < G->vexnum; ++j) {
            if (!S[j] && dist[j] < min) {
                u = j;
                min = dist[j];
            }
        }
        S[u] = 1;
        for (j = 0; j < G->vexnum; ++j) {
            if (!S[j] && dist[u] + G->arcs[u][j] < dist[j]) {
                dist[j] = dist[u] + G->arcs[u][j];
                path[j] = u;
            }
        }
    }
}

// 输出任一对顶点间的最短路径及路径长度
void PrintPath(MGraph *G, int path[][MAX_VERTEX_NUM], int dist[][MAX_VERTEX_NUM]) {
    int i, j, k;
    for (i = 0; i < G->vexnum; ++i) {
        for (j = 0; j < G->vexnum; ++j) {
            if (i != j) {
                printf("%d到%d的最短路径为：", G->vertices[i], G->vertices[j]);
                k = path[i][j];
                if (k == -1) {
                    printf("无路径\n");
                } else {
                    printf("%d", G->vertices[i]);
                    while (k != -1) {
                        printf("->%d", G->vertices[k]);
                        k = path[k][j];
                    }
                    printf("->%d，长度为：%d\n", G->vertices[j], dist[i][j]);
                }
            }
        }
    }
}

// 输出某一顶点到其他各顶点间的最短路径及路径长度
void PrintDijkstra(MGraph *G, int v, int path[], int dist[]) {
    int i;
    printf("从%d出发到各顶点的最短路径为：\n", G->vertices[v]);
    for (i = 0; i < G->vexnum; ++i) {
        if (i != v) {
            printf("%d到%d的最短路径为：", G->vertices[v], G->vertices[i]);
            if (path[i] == -1) {
                printf("无路径\n");
            } else {
                printf("%d", G->vertices[i]);
                int j = i;
                while (j != v) {
                    printf("<-%d", G->vertices[path[j]]);
                    j = path[j];
                }
                printf("<-%d，长度为：%d\n", G->vertices[v], dist[i]);
            }
        }
    }
}

int main() {
    MGraph G;
    int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM], dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int v, path1[MAX_VERTEX_NUM], dist1[MAX_VERTEX_NUM];
    CreateMGraph(&G);
    Floyd(&G, path, dist);
    PrintPath(&G, path, dist);
    printf("请输入起点的下标：");
    scanf("%d", &v);
    Dijkstra(&G, v, path1, dist1);
    PrintDijkstra(&G, v, path1, dist1);
    return 0;
}

注：本代码中使用了邻接矩阵来创建无向网。在Floyd算法中，path数组存放的是中间节点的下标（如果中间节点为-1，则表示i到j之间不存在路径），dist数组存放的是i到j的最短距离。在Dijkstra算法中，path数组存放的是每个顶点的前驱节点的下标（如果前驱节点为-1，则表示从v到该顶点不存在路径），dist数组存放的是从v到每个顶点的最短距离。

用Dijkstra（迪杰斯特拉算法），求下图中从顶点0到其他各顶点的最短路径,完成表格填写

首先，我们需要构建邻接矩阵表示图：

   0  1  2  3  4
0  0  10 0  30 100
1  0  0  50 0  0
2  0  0  0  0  10
3  0  0  20 0  60
4  0  0  0  0  0

然后，我们使用迪杰斯特拉算法求出从顶点0到其他各顶点的最短路径：

| 已确定最短路径的顶点集合 | 0 | 0,1 | 0,1,2 | 0,1,2,3 | 0,1,2,3,4 |
| --- | --- | --- | --- | --- | --- |
| 最短路径长度 | 0 | 10 | 20 | 30 | 90 |
| 最短路径 | 0 | 0-1 | 0-1-2 | 0-3 | 0-3-2-4 |

因此，从顶点0到其他各顶点的最短路径为：

- 0-0，长度为0
- 0-1，长度为10
- 0-1-2，长度为20
- 0-3，长度为30
- 0-3-2-4，长度为90