BFS
BFS广度优先搜索算法
核心思想
从源点出发，每次选择跟当前点直连的邻点放入队列中，再一一根据FIFO先进先出的原则依次取出队列中的点进行处理。
特征
- 1、基于FIFO先进先出的算法思想
- 2、单源路径，也就是只能得到给定的一个源点到其他任意节点的距离
适用范围
- 1、只能处理权值相同的无向图
Dijkstra算法：
dijkstra算法是一种经典的基于贪心的单源最短路算法。
核心思想
从源点出发，每次选择离源点最近的一个顶点前进，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。
特征
- 1、基于贪心算法思想
- 2、单源路径，也就是只能得到给定的一个源点到其他任意节点的距离
适用范围
- 1、不能处理负权边或环
- 2、可以处理正权边
- 3、可以处理无向图和有向图
注：为什么不能有负权边
Dijkstra算法当中将节点分为已求得最短路径的集合（记为P）和未确定最短路径的集合（记为Q），归入P集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与P内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度(意思是原先从a0—a已经确定一个最短路径，而此时的边权值为负，则此步骤中的边权计算结果必定小于已经确定了的路径长度)，但是a在Dijkstra算法下是无法更新的，由此便可能得不到正确的结果。
解题步骤
- 1、初始化邻接矩阵
- 2、初始化还未确定最短路径的节点列表
- 3、双重循环：
-
最外层为除源点之外的其他节点的遍历 -
里面为遍历和更新未确定距离的节点列表的遍历 - 3.1、从还未确定最短路径的节点列表中找出距离源点最近的节点
- 3.2、更新还未确定最短路径的节点列表
- 3.3、根据找到的这个最短路径节点，更新每一个还未确定最短路径的节点到源点的距离
- 4、根据题目要求计算结果
下面以网络延迟时间为例
class Solution(object):
def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
# 说明：
# (u, v)表示节点u到节点v的路径
# 初始化邻接矩阵：
# graph是一个二维矩阵，graph[u][v]表示(u, v)路径的花费
graph = [[float("inf") for _ in range(N+1)] for _ in range(N+1)]
for u, v, t in times:
graph[u][v] = t
# 源点到自己的花费为0
graph[K][K] = 0
# 标记哪些还没有确定最短路径的节点列表
unmark = [i for i in range(N+1) if i != K]
# 需要确定除源点以外的其他节点到源点的最少花费，因此需要N-1次循环
for _ in range(1, N):
min_time = float("inf")
min_node = 0
# 从还没有确定最少花费的节点列表中找出距离源点最少花费的那个节点
for i in unmark:
if graph[K][i] < min_time:
min_time = graph[K][i]
min_node = i
# 最少花费节点已找到并确定，因此需要从还没有确定花费的节点列表中移除
unmark.remove(min_node)
# 通过找到的这个最少花费节点，更新每一个还没有确定花费的节点到源点的最少花费
# 也就是看把这个节点作为中间跳是否更少花费
for i in unmark:
graph[K][i] = min(graph[K][i], graph[K][min_node] + graph[min_node][i])
max_time = 0
# 遍历各个节点：选出节点K到所有节点的最大花费，即为整个网络的最大花费。
for i in range(1, N+1):
if i != K:
max_time = max(max_time, graph[K][i])
# 需要判断是否网络不通
return -1 if max_time == float("inf") else max_timeFloyd
是一种基于动态规划的多源最短路算法。
核心思想
从任意节点u到任意节点v的最短路径有2种：
- 1是直接从u到v
- 2是从u经过若干个节点k到v
所以，我们假设graph(u,v)为节点u到节点v的最短路径的距离(当然，不同的题目代表的不一样，比如有的可能是花费，需要灵活变通)，对于每一个节点k(1~N个节点)，我们检查graph(u,k) + graph(k,v) < graph(u,v)是否成立，如果成立，证明从u到k再到v的路径比u直接到v的路径短，我们便设置graph(u,v) = graph(u,k) + graph(k,v)，当我们遍历完所有节点k，graph(u,v)中记录的便是u到v的最短路径的距离。
特征
- 1、基于动态规划
- 2、时间复杂度为O(n^3)
- 3、空间复杂度为O(n^2)
- 4、多源路径，也就是可以得到任意顶点对之间的最短路径
适用范围
- 1、可以处理负权边
- 2、不能处理负权环
- 3、可以处理无向图和有向图
解题步骤
- 1、初始化邻接矩阵
- 2、三重循环：
-
最外层为中间节点k的遍历 -
里面两层分别为节点u和节点v的遍历 - 2.1、根据k为中间跳节点更新(u, v)的最短距离
- 3、根据题目要求计算结果
下面以网络延迟时间为例
class Solution(object):
def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
# 说明：
# (u, v)表示节点u到节点v的路径
# (u, k)表示节点u到节点k的路径
# (k, v)表示节点k到节点v的路径
# 初始化邻接矩阵：
# graph是一个二维矩阵，graph[u][v]表示(u, v)路径的花费
graph = [[float("inf") for _ in range(N+1)] for _ in range(N+1)]
for u, v, t in times:
graph[u][v] = t
# 该层循环为(u, v)路径的各个中间跳节点
for k in range(1, N+1):
# 该层循环为(u, v)路径的各个u节点
for u in range(1, N+1):
# 该层循环为(u, v)路径的各个v节点
for v in range(1, N+1):
# 如果(u, v)路径的花费比借助k节点跳跃的路径(即先(u, k)，再(k, v))花费更少，则更新(u, v)的最小花费
graph[u][v] = min(graph[u][v], graph[u][k] + graph[k][v])
max_time = 0
# 遍历各个节点：选出节点K到所有节点的最大花费，即为整个网络的最大花费。
for i in range(1, N+1):
if i != K:
max_time = max(max_time, graph[K][i])
# 需要判断是否网络不通
return -1 if max_time == float("inf") else max_time后记
最短路径问题是图论研究中的一个经典算法问题。因此针对图最短路径问题先后提出了许多算法。各类算法的应用场景不尽相同。
- 1、
Dijkstra算法和Bellman-Ford算法用于解决单源最短路径； - 2、
Floyd算法可以解决多源最短路径； - 3、
Dijkstra算法适用稠密图（邻接矩阵），因为稠密图问题与顶点关系密切； - 4、
Bellman-Ford算法适用稀疏图（邻接表），因为稀疏图问题与边关系密切； - 5、
Floyd算法在稠密图（邻接矩阵）和稀疏图（邻接表）中都可以使用。
当然还有其他的一些算法，不一一说明了。
今天的这篇文章主要讲解了Dijkstra算法和Floyd算法，其他的有时间再更新吧。
