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

您好！对于给定的图的邻接矩阵，可以使用迪杰斯特拉算法或弗洛伊德算法来求解顶点间的最短路径。

1. 迪杰斯特拉算法：
- 初始化一个距离数组dist，表示源点到各顶点的最短距离。将源点距离设为0，其他顶点距离设为无穷大。
- 初始化一个集合visited，存储已经求得最短路径的顶点。
- 重复以下步骤，直到visited包含所有顶点：
- 在未访问的顶点中，选择距离源点最近的顶点u，并将其加入visited集合。
- 更新与顶点u相邻的顶点v的最短距离，如果通过顶点u可以使得v的距离更短，则更新dist[v]的值。
- 最终，dist数组中存储的就是源点到各顶点的最短距离。

2. 弗洛伊德算法：
- 初始化一个距离矩阵dist，表示任意两个顶点之间的最短距离。如果两个顶点之间存在边，则距离为边的权重，否则为无穷大。
- 通过三重循环，依次考虑所有顶点作为中间点，尝试更新两个顶点之间的最短距离。如果通过中间点可以使得两个顶点之间的距离更短，则更新dist矩阵中的值。
- 最终，dist矩阵中存储的就是任意两个顶点之间的最短距离。

以上是使用迪杰斯特拉算法和弗洛伊德算法求解图中顶点间最短路径的方法。如果您有具体的图的邻接矩阵和顶点信息，我可以帮您进一步解答。

相关问题

用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