单源最短路

无权图最短路径

这个简单，BFS求解就好。像之前BFS章节提到的，BFS可以从一个点出发寻找无权有向或无向图的最短距离。

# look for shortest path from start -> u
queue = [(start, 0)]
vis = set([start])
while queue:
    v, cost = queue.pop(0)
    if v==u: return cost
    for u in graph[v]:
        if u in vis: continue
        queue.append(u)
return -1

如果要打印打印从start到u的最短路径，与之前的BFS算法一样，我们用要path来记录路径和标记已访问的点。或者如果要节省一下path中存储路径的空间，我们可以用先驱数组来表示路径（参考代码见CP-Algorithms）。

BFS求解无权图最短路径可以理解成加权图最短路径中权重均为1的特殊情况。

加权图最短路径

假设所有边的权重都>0，那么Dijkstra最短路算法是一种自然的贪心算法。

# 求"给予起点start和目的地u的最短路径"
dist = {start: 0}      # 最小dist
queue = [(0, start)]   # 最小dist堆
vis = set()            # 访问过的点

while queue:
    cost, v = heapq.heappop(queue)
    if v in vis: continue
    vis.add(v)
    for n, wt in graph[v]:
        ncost = cost + wt
        if ncost < dist.get(n, float('inf')):
            dist[n] = ncost
            heapq.heappush(queue, (ncost, n))
return dist

如果是求从start到所有点的单源最短路径，我们不要提前返回，最后在dist数组里就有所有答案。其实可以证明，Dijkstra算法解决的单源最短路径是解决一下问题的最好方法：

1. 单源最短路（上例）：给定起始点start，求到所有可达点的最短路径

2. 单目的地最短路：把目的地当成起点，和情况1等价

3. 给予起点和终点的最短路径：到达目的地后提前返回

• 其他实现方法：用PQ实现的Dijkstra似乎有很多种写法。其中Wikipedia和《算法导论》有更简单的实现，然而需要Decrease Key的操作。这一点在Python的heapq库中并没有直接的实现。

• 有负权重边的情况：两个节点u与v之间有最短路径，那么路径中不应该路过任何在负权重环中的节点。如果符合这样的条件，我们可以用Bellman-Ford算法来解决。

K 站中转内最便宜的航班

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，
你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。
如果没有这样的路线，则输出 -1。

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200

# Dijkstra
graph = defaultdict(list)
for a, b, cost in flights:
    graph[a].append((b, cost))

queue = [(0, src, 0)]
vis = {(src, 0): 0}
while queue:
    cost, point, stop = heapq.heappop(queue)
    if point == dst: return cost
    for nei, c in graph[point]:
        ncost = cost + c
        nstop = stop + 1
        if nstop <= k+1 and ncost < vis.get((nei, nstop), float('inf')):
            vis[nei] = ncost
            heapq.heappush(queue, (ncost, nei, nstop))
return -1

# DP
# f[i][k] is the minimum cost to get to node i after k stops, self included
# f[i][k] = min(f[i][k], f[j][k-1]+w),
# given i and j are connected with weight w
f = [[float('inf')]*(K+2) for _ in range(n)]
f[src][0] = 0
for k in range(1, K+2):
    for j, i, w in flights:
        f[i][k] = min(f[i][k], f[j][k-1]+w)
res = min(f[dst])
return res if res < float('inf') else -1

从第一个节点出发到最后一个节点的受限路径数 [LC1786]

用最短路算法求解shortestPath以后，记忆化DFS搜索答案。

现有一个加权无向连通图。给你一个正整数 n ，表示图中有 n 个节点，并按从 1 到 n 给节点编号；
另给你一个数组 edges ，其中每个 edges[i] = [ui, vi, weighti] 
表示存在一条位于节点 ui 和 vi 之间的边，这条边的权重为 weighti 。

从节点 start 出发到节点 end 的路径是一个形如 [z0, z1, z2, ..., zk] 的节点序列，
满足 z0 = start 、zk = end 且在所有符合 0 <= i <= k-1 的节点 zi 和 zi+1 
之间存在一条边。

路径的距离定义为这条路径上所有边的权重总和。用 distanceToLastNode(x) 
表示节点 n 和 x 之间路径的最短距离。
受限路径 为满足 distanceToLastNode(zi) > distanceToLastNode(zi+1) 的一条路径，
其中 0 <= i <= k-1 。

返回从节点 1 出发到节点 n 的 受限路径数。
由于数字可能很大，请返回对 109 + 7 取余 的结果。

class Solution:
    def shortestPath(self, graph, start):
        dist = {start: 0}
        queue = [(0, start)]
        vis = set()
        while queue:
            cost, v = heapq.heappop(queue)
            if v in vis: continue
            vis.add(v)
            for n, wt in graph[v]:
                ncost = cost + wt
                if ncost < dist.get(n, float('inf')):
                    dist[n] = ncost
                    heapq.heappush(queue, (ncost, n))
        return dist
    
    def getGraph(self, edges):
        # make adjacency list from edges
        graph = defaultdict(list)
        for i, j, w in edges:
            graph[i-1].append((j-1, w))
            graph[j-1].append((i-1, w))
        return graph
        
        
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
        graph = self.getGraph(edges)
        dist = self.shortestPath(graph, n-1)

        @cache
        def getNumPaths(v):
            if v==n-1: return 1
            ret = 0
            for u, _ in graph[v]:
                if dist[u] < dist[v]:
                    ret += getNumPaths(u)
            return ret
        return getNumPaths(0) % (10**9 + 7)