最短路径查找Dijkstra算法

最短路径查找Dijkstra算法

1、解决的是最短路径问题。

      从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径。其实dijkstra算法在交通中应用还是相对广泛的，可以用于需要车辆从a点到b点的最短路径(list)。

2、算法的特点：

       使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

3、实例(步骤拆分，以无向图为例)

统一思路：

      ●每次从未标记的节点中选择距离出发点最近的节点，标记，收录到最优路径集合中。

      ●计算刚加入节点A的邻近节点B(不包含标记的节点)的距离，如果(节点A的距离+节点A到节点B的边长) < 节点B的距离，就更新节点B的距离和前面点。

     其中0为起点，4为终点。

第一步：

     距离起始节点0(或者出发点)距离最近的，当然是0，首先标记0号节点。

 第二步：

      从起始节点0开始，0的临界节点是①和⑦，距离初始节点距离分别是4和8。然后在未标记点中，寻找距离出发点最近的点，作为标记点。

      ①在未标记点中，find离出发点0距离最近，标记节点①，收录到最优路径节点中。并更新新标记的节点①的临近节点。

第三步：

     节点①的临近节点分别是节点②和节点⑦，到节点①的边长分别为8和11。从节点0出发到②的最优路径，经过节点①的话，4+8 < 无穷大，则更新②到出发点的距离，并更新②前边的节点：①

     假如从出发点0经过节点①到节点⑦，这个距离为4+11=15，这个距离 > 节点⑦本来的距离，所以说节点⑦不更新(大于或等于都不更新)

    从未标记的点中， find离出发点0距离最近，标记节点⑦，收录到最优路径节点中。并更新新标记的节点⑦的临近节点。

第四步：

     上一步更新点⑦，临近节点⑧和⑥离出发点0的距离。

     临近节点⑧和⑥的距离分别是15和9，都比无穷大要小，更新。

    对比未标记节点，标记节点⑥，并计算⑥的邻近节点⑤和⑧，分别是11、15。

    同样标记节点⑤，计算⑤的邻近节点距离

循环上述的操作：

  最终得出，最短路径是21，路径节点顺序(从目的节点倒着推：④⑤⑥⑦) 顺序如下图：

 代码：

import math
V = 6
# 标记数组：used[v]值为False说明改顶点还没有访问过，在S中，否则在U中！
used = [False for _ in range(V)]
# 距离数组：distance[i]表示从源点s到ｉ的最短距离，distance[s]=0
distance = [float('inf') for _ in range(V)]
# cost[u][v]表示边e=(u,v)的权值，不存在时设为INF
# cost领接表
cost = [[float('inf') for _ in range(V)] for _ in range(V)]
def dijkstra(s):distance[s] = 0while True:# v在这里相当于是一个哨兵，对包含起点s做统一处理！v = -1# 从未使用过的顶点中选择一个距离最小的顶点for u in range(V):if not used[u] and (v == -1 or distance[u] < distance[v]):v = uif v == -1:# 说明所有顶点都维护到S中了！break# 将选定的顶点加入到S中, 同时进行距离更新used[v] = True# 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。for u in range(V):distance[u] = min(distance[u], distance[v] + cost[v][u])# if __name__ == '__main__':
#
for _ in range(9):v, u, w = list(map(int, input().split()))cost[v][u] = wcost[u][v] = w
s = int(input('请输入一个起始点：'))
dijkstra(s)
print(distance)