三叶最短路径问题博客 "跟着大哥混有饭吃"
1.图1(跟着三叶学图论最短路算法)
这是 LeetCode 上的「743. 网络延迟时间」，难度为「中等」
有 n 个网络节点，标记为1到 n。
给你一个列表times，表示信号经过 有向 边的传递时间。times[i] = (ui, vi, wi)，其中ui是源节点，
vi是目标节点， wi是一个信号从源节点传递到目标节点的时间。
现在，从某个节点K发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回-1 。
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都 互不相同（即，不含重复边）
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
times = [[1,2,1]], n = 2, k = 1
times = [[1,2,1]], n = 2, k = 2
没办法自己不会分析,只能学三叶的分析,假装我会了!!!
做题首先: 看题目给出的条件,条件k < n <= 100 也就是节点>= 100, times.length <= 6000 边>= 6000
[从某个节点K发出一个信号。需要多久才能使所有节点都收到信号?] 这句话什么意思呢?
举个例子:
比如太阳到地球需要10s, 到月球需要5s, 到火星需要8s, 那么太阳光最短几秒可以照射到这三个星球,
直接取太阳光带最远的星球花的时间是不是就好了,也就是到地球的10s.这个题是一个意思,我们只需要求出k点发出的信号到最远的地方所花的时间就好了.
# 存图方式: 重点***** m 表示节点数, n表示边数
1. 邻接矩阵(二维数组存图,很方便理解和观看,但是消耗很大,耗时很长O(m**2))
chart = [[0 for _ in range(n)] for _ in range(n)]
def add(src, dest, weight):
chart[src][dest] = weight
2.邻接表(链表形式存图, 非常适合稀疏图, 消耗很小O(m+n))
下面我举了一个列子方便理解:
n = 6 # 节点
m = 10 # 边 一般会设置大点
edges = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
edges = [[4, 1, 1], [1, 2, 3], [0, 3, 2], [0, 4, 10], [3, 1, 1], [1, 4, 3]]
idx = 0 # 边编号
he = [-1 for _ in range(n)]
e = [0 for _ in range(m)]
ne = [0 for _ in range(m)]
w = [0 for _ in range(m)]
def add(src, dest, weight):
nonlocal idx
e[idx] = dest # 当前边指向的节点dest
ne[idx] = he[src] # 链表的上一个边对应的idx
he[src] = idx # 当前起始节点指向的边
w[idx] = weight # 当前边的权重
idx += 1
""" 先看代码,熟悉一下看下面解释,看不懂继续看while循环代码
同一个起点, 对应的边的链表:比如从9->3 9 ->4
idx=0:
e[0] = 3 0号边指向3号节点
ne[0] = he[9] = -1 -1表示结束
he[9] = 0 9号节点指向0号边
w[0] = x 0号边的权重
idx = 1
e[1] = 4 1号边指向4号节点
ne[1] = he[9] = 0 1号边的上一个边是0号边
he[9] = 1 9号节点执行1号边
w[1] = x 1号边的权重
最后发现每he[n] n一直都表示的其实当前节点, 只不过he[n]的值一直在变换( 相当于链表头结点插入值), he[n]一直更换头结点
idx = ne[he[n]] 指向的是他的下一个边的编号, 通过这个编号, 我们可以通过dest = e[idx], dest就是n指向的一个节点
之后在通过ne[idx]拿到下一个idx的编号,一直到节点为-1
9 -> 4 -> 3 -> -1 看不懂下面有代码while循环中的代码
"""
for edge in edges:
add(edge[0], edge[1], edge[2])
# 上面解释不是很清楚,直接上代码
i = he[0] # 以0号节点为例, i = he[0]取出0号节点的指向的头节点(也就是一个边的编号)(链表里面存储的是边的编号)
while i != -1:
b = e[i] # e中存储的i号边指向的节点
c = w[i] # w中存储的是i号边的权重
print(b, c)
i = ne[i] # ne存储0号节点的下一个边(这些边都是从0号节点出发的,只不是使用数组代替链表存储了他们)
3.类(这个方式很少用, O(m))
class Edge(object):
def __init__(self, src, dest, weight):
self.src = src
self.dest = dest
self.weight = weight
1.Floyd 算法(邻接矩阵)
Floyd 算法主要分三步:
1.初始化图
distance = [[INF for _ in range(M)] for _ in range(M)]
distance[i][j] = distance[j][i] = 0 if i == j else INF # i,j 相等就是同有个节点, 所以为0
2.填充值 (将给出的节点边权关系填充进去)
for item in times:
s, t , c = item[0], item[1], item[2]
distance[s][t] = c
3.dis[i][j]存储从i->j的最小距离
他有一个更新条件 if dis[i][j] > dis[i][p] + dis: dis[i][j] = dis[i][p] + dis, 其实就是根据三角形边推出来的,其中p是中间过渡节点, 所以需要遍历
Floyd 算法会将所有节点之间的最短路径都求出来, 之后只要遍历dist[k][x], 找出k点到其他x节点(需要遍历)的最大值就好了
def floyd(dis):
for p in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
dis[i][j] = min(dis[i][j], dis[i][p] + dis[p][j])
class Solution(object):
def networkDelayTime(self, times, n, k):
"""
:type times: List[List[int]]
:type n: int
:type k: int
:rtype: int
https://zhuanlan.zhihu.com/p/339542626 Floyd 算法
"""
M = 110
INF = float("inf")
distance = [[INF for _ in range(M)] for _ in range(M)]
# 初始化图
for i in range(1, n + 1):
for j in range(1, n + 1):
distance[i][j] = distance[j][i] = 0 if i == j else INF
# 邻接矩阵图
for item in times:
s, t , c = item[0], item[1], item[2]
distance[s][t] = c
def floyd(dis):
for p in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
dis[i][j] = min(dis[i][j], dis[i][p] + dis[p][j])
floyd(distance)
ans = 0
for i in range(1, n + 1):
ans = max(ans, distance[k][i])
return ans if ans != INF else -1
1.Dijkstra（邻接矩阵)
"""743. 网络延迟时间"""
class Solution(object):
def networkDelayTime(self, times, n, k):
INF = float("inf")
w = [[0 for _ in range(n)] for _ in range(n)] # 节点之间的权重
dist = [INF for _ in range(n)] # 从初始节点到n节点的最多距离
# 初始化图
for i in range(n):
for j in range(n):
w[i][j] = 0 if i == j else INF
# 添加边权关系
for item in times:
s, t, c = item[0] - 1, item[1] - 1, item[2] # 以为题目是1->n, 需要-1变成0->n-1
w[s][t] = c
dist[k-1] = 0
vis = [False for _ in range(n)]
for i in range(n-1): # 遍历次数,为节点次数, 每个节点都需要
x = -1 # 找没被表示的节点,以该节点更新其他节点与初始节点的距离
for p in range(n):
if not vis[p] and (x == -1 or dist[p] < dist[x]): x = p
vis[x] = True
for p in range(n):
dist[p] = min(dist[p], dist[x] + w[x][p])
ans = max(dist)
return -1 if ans >= INF / 2 else ans
1.Dijkstra（邻接表）
class Node(object):
def __init__(self, x, val):
self.x = x
self.v = val
def __gt__(self, other):
return self.v > other.v
"""743. 网络延迟时间"""
class Solution(object):
def __init__(self):
self.n = 110
self.m = 6010
self.INF = float("inf")
self.e = [0 for _ in range(self.m)]
self.ne = [0 for _ in range(self.m)]
self.he = [-1 for _ in range(self.n)]
self.w = [0 for _ in range(self.m)]
self.dist = [self.INF for _ in range(self.n)] # 从初始节点到n节点的最多距离
self.idx = 0
def add(self, src, dest, weight):
self.e[self.idx] = dest
self.ne[self.idx] = self.he[src]
self.he[src] = self.idx
self.w[self.idx] = weight
self.idx += 1
def networkDelayTime(self, times, n, k):
"""堆优化 Dijkstra（邻接表）"""
import heapq
heap = []
# 存图
for item in times:
self.add(item[0], item[1], item[2])
vis = [False for _ in range(self.n)]
heapq.heappush(heap, Node(k, 0))
self.dist[k] = 0
while heap:
t: Node = heapq.heappop(heap)
node, _ = t.x
if vis[node]: continue
vis[node] = True
i = self.he[node]
while i != -1:
j = self.e[i] # 下一个节点
if self.dist[j] > self.dist[node] + self.w[i]:
self.dist[j] = self.dist[node] + self.w[i]
heapq.heappush(heap, Node(j, self.dist[j]))
i = self.ne[i] # 获取下一个边
ans = max(self.dist[1:n+1])
return -1 if ans >= self.INF / 2 else ans
s1 = Solution()
times = [[2,1,1],[2,3,1],[3,4,1]]; n = 4; k = 2
ret = s1.networkDelayTime(times, n, k)
print(ret)
1.Bellman Ford（类）
"""743. 网络延迟时间"""
class Edge(object):
def __init__(self, src, dest, weight):
self.src = src
self.dest = dest
self.w = weight
class Solution(object):
def networkDelayTime(self, times, n, k):
"""Bellman Ford（类 & 邻接表）"""
INF = float("inf")
w = [[0 for _ in range(n)] for _ in range(n)] # 节点之间的权重
dist = [INF for _ in range(n+1)] # 从初始节点到n节点的最多距离
# 初始化图
for i in range(n):
for j in range(n):
w[i][j] = 0 if i == j else INF
# 添加边权关系
for item in times:
s, t, c = item[0] - 1, item[1] - 1, item[2] # 以为题目是1->n, 需要-1变成0->n-1
w[s][t] = c
dist[k] = 0
for i in range(n):
new_dist = dist[:] # 确保本次操作不影响之前的dist数据
for edge in times:
src, dest, weight = edge
dist[dest] = min(dist[dest], new_dist[src] + weight)
ans = max(dist[1:])
return -1 if ans >= INF / 2 else ans
s1 = Solution()
times = [[2,1,1],[2,3,1],[3,4,1]]; n = 4; k = 2
ret = s1.networkDelayTime(times, n, k)
print(ret)
1. Bellman Ford 邻接表
class Solution(object):
def __init__(self):
self.n = 110
self.m = 6010
self.INF = float("inf")
self.e = [0 for _ in range(self.m)]
self.ne = [0 for _ in range(self.m)]
self.he = [-1 for _ in range(self.n)]
self.w = [0 for _ in range(self.m)]
self.dist = [self.INF for _ in range(self.n)] # 从初始节点到n节点的最多距离
self.idx = 0
def add(self, src, dest, weight):
self.e[self.idx] = dest
self.ne[self.idx] = self.he[src]
self.he[src] = self.idx
self.w[self.idx] = weight
self.idx += 1
def networkDelayTime(self, times, n, k):
# 存图
for item in times:
self.add(item[0], item[1], item[2])
self.dist[k] = 0
for p in range(1, n+1):
new_dist = self.dist[:]
for q in range(1, n+1):
i = self.he[q]
while i != -1:
b = self.e[i]
self.dist[b] = min(self.dist[b], new_dist[q] + self.w[i])
i = self.ne[i]
ans = max(self.dist[1:n+1])
return -1 if ans >= self.INF / 2 else ans
s1 = Solution()
times = [[2,1,1],[2,3,1],[3,4,1]]; n = 4; k = 2
ret = s1.networkDelayTime(times, n, k)
print(ret)
1.SPFA（邻接表)
https://blog.csdn.net/m15738518751/article/details/47805003 这个细节讲得很好,但是没图
https://www.cnblogs.com/shadowland/p/5870640.html 这个图很好,但是没讲细节
class Solution(object):
def __init__(self):
self.n = 110
self.m = 6010
self.INF = float("inf")
self.e = [0 for _ in range(self.m)] # 某一条边指向的节点
self.ne = [0 for _ in range(self.m)] # 当前边指向的下一个边索引
self.he = [-1 for _ in range(self.n)] # 头结点对应的边
self.w = [0 for _ in range(self.m)] # 权重
self.dist = [self.INF for _ in range(self.n)] # 从初始节点到n节点的最多距离
self.idx = 0
self.vis = [False for _ in range(self.n)]
def add(self, src, dest, weight):
self.e[self.idx] = dest
self.ne[self.idx] = self.he[src]
self.he[src] = self.idx
self.w[self.idx] = weight
self.idx += 1
def networkDelayTime(self, times, n, k):
# 存图
import queue
for item in times:
self.add(item[0], item[1], item[2])
self.dist[k] = 0
heap_q = queue.SimpleQueue()
heap_q.put(k)
self.vis[k] = True
while not heap_q.empty():
cur = heap_q.get()
self.vis[cur] = False # 当前节点拿出来之后,就可以把self.vis置位False了
new_dist = self.dist[:]
i = self.he[cur] # 当前节点指向的边的头idx
while i != -1:
b = self.e[i] # 指向的节点
if self.dist[b] > new_dist[cur] + self.w[i]:
if not self.vis[b]: # 如果下一个节点没在则加入heap_q, 否则只更新距离即可
heap_q.put(b)
self.vis[b] = True
self.dist[b] = new_dist[cur] + self.w[i]
i = self.ne[i]
ans = max(self.dist[1:n+1])
return -1 if ans >= self.INF / 2 else ans
s1 = Solution()
times = [[2,1,1],[2,3,1],[3,4,1]]; n = 4; k = 2
ret = s1.networkDelayTime(times, n, k)
print(ret)