用迪杰斯特拉算法求无向网的最短路径

迪杰斯特拉算法是一种解决带权有向图中单源最短路径的经典算法，也可以用来解决无向网的最短路径问题。其基本思想是从起点开始，逐步扩展到其他顶点，直到所有顶点都被标记为已确定最短路径的顶点。具体实现步骤如下：

1. 定义一个数组dist[]，dist[i]表示从起点到顶点i的最短路径长度，初始化为无穷大，dist[s]=0，其中s为起点。
2. 定义一个数组visited[]，visited[i]表示顶点i是否已经被标记为已确定最短路径的顶点，初始化为false。
3. 从dist[]中找到当前未被标记的dist[i]最小的顶点u，标记visited[u]=true。
4. 遍历所有与u相邻的顶点v，如果visited[v]=false，且从起点到u再到v的路径长度小于dist[v]，则更新dist[v]=dist[u]+w(u,v)，其中w(u,v)为边(u,v)的权值。
5. 重复步骤3和步骤4，直到所有顶点都被标记为已确定最短路径的顶点。

最终得到的dist[]数组就是起点到所有顶点的最短路径长度。

相关问题

迪杰斯特拉算法无向网

迪杰斯特拉算法是一种用于解决带权有向图或无向图的单源最短路径问题的算法。下面是迪杰斯特拉算法在无向网中的实现过程：

1.初始化：将源点到各个顶点的距离初始化为无穷大，将源点到自身的距离初始化为0。

2.找到源点到各个顶点的最短路径：从源点开始，依次遍历与源点相邻的顶点，更新源点到这些顶点的距离。然后从这些顶点中选择距离最短的顶点作为下一个要遍历的顶点，重复这个过程，直到遍历完所有的顶点。

3.输出最短路径：根据源点到各个顶点的距离，输出源点到各个顶点的最短路径。

下面是一个使用Python实现的迪杰斯特拉算法的例子，假设我们要求解以下无向网的以4为源点的最短路径：

     2
  1-----2
  |\   /|\
  | \ / | \
3|  4  |5 \4
  | / \ | /
  |/   \|/
  3-----4
     1

import sys

# 定义一个函数，用于找到源点到各个顶点的最短路径
def dijkstra(graph, src):
    # 初始化距离列表
    dist = [sys.maxsize] * len(graph)
    dist[src] = 0
    # 初始化访问列表
    visited = [False] * len(graph)
    # 遍历所有顶点
    for i in range(len(graph)):
        # 找到距离源点最近的顶点
        min_dist = sys.maxsize
        for j in range(len(graph)):
            if not visited[j] and dist[j] < min_dist:
                min_dist = dist[j]
                u = j
        # 标记该顶点已访问
        visited[u] = True
        # 更新源点到相邻顶点的距离
        for v in range(len(graph)):
            if not visited[v] and graph[u][v] != 0 and dist[u] + graph[u][v] < dist[v]:
                dist[v] = dist[u] + graph[u][v]
    # 输出最短路径
    for i in range(len(dist)):
        print("源点到顶点%d的最短距离为：%d" % (i, dist[i]))

# 定义一个邻接矩阵，表示上面的无向网
graph = [[0, 1, 3, 0, 0],
         [1, 0, 2, 5, 4],
         [3, 2, 0, 3, 0],
         [0, 5, 3, 0, 4],
         [0, 4, 0, 4, 0]]

# 调用dijkstra函数，求解以4为源点的最短路径
dijkstra(graph, 4)

输出结果为：

源点到顶点0的最短距离为：4
源点到顶点1的最短距离为：4
源点到顶点2的最短距离为：3
源点到顶点3的最短距离为：4
源点到顶点4的最短距离为：0

用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到每个顶点的最短距离。