算法（八）最短路径

2018-12-10

本文简单介绍一下最短路径算法，包括Dijkstra和Floyd

1. Dijkstra算法

1.1 简介

Dijkstra算法

统计起始点都各个节点的最短路径

dist[i]存储从起始点x到i的最短距离
先初始化dist为最大值，dist[x] = float(“inf”)
然后遍历起始点x的相邻节点i，如果距离dist[x]+edge[i][x] < dist[i]，更新dist[i]
然后将x标记为已经访问，从距离起始点x最近的点继续做轮询。

注意：迪克斯特拉算法只适用于正权重的情况，不能用于负权重

1.2 参考

动态图： https://zhuanlan.zhihu.com/p/34624812

1.3 举例分析

题目

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。

指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。

如果不存在从 start 到 end 的路径，请返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:

        graph = collections.defaultdict(list)

        for k, v in enumerate(edges):
            graph[v[0]].append((v[1], succProb[k]))
            graph[v[1]].append((v[0], succProb[k]))
        
        visited = set()
        dist = [0] * n
        pq = []
        
        # python heapq是小顶堆，所以需要取反
        heapq.heappush(pq, (-1, start))
        
        while pq:
            (cost, node) = heapq.heappop(pq)
            visited.add(node)

            for x in graph[node]:
                if x[0] not in visited and -x[1] * cost > dist[x[0]]:
                    dist[x[0]] = -x[1] * cost
                    heapq.heappush(pq, (x[1]*cost, x[0]))
        return dist[end]

2. Floyd算法

目的是求解任意两点的最短路径，核心思想是经过任意数量的节点进行中转，检查路径是否为最短

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if e[i][j] > e[i][k] + e[k][j]:
                e[i][j] = e[i][k] + e[k][j]