迪杰斯特拉算法无向网

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

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