---

title:Graph Algorithm
date:2023-12-25 22:01:49
tags:Computer science

基本图算法

一. 单源最短路径

1. Dijistra算法–有向无环图中的单源最短路问题

1.1 算法描述

Dijistra算法是一种贪心算法，贪心策略的选择如下：

• 遍历到u时，到u的所有路径上的节点已经生成最小路径：设w是从v0到u的路径上的结点，由于到u的路径一定经过S中的结点，根据生成规则，按非降次序生成最小路径，所以w一定在S集合中，所以在v0到u的路径上的点都已经生成最小路径；
• 入边的选择：生成的下一条路径的终点u是S外dist(u)最小的结点（按非降次序）；
• 更新最小路径：（实际上这一步也叫松弛，更新的dist值是最小路径估计）如果找到这样的u且生成了从v0到u的最短路径,将u加入集合S。此时从v0经过u终点为S外一点u的最小路径可能会变小，因为可能经过u到w的路径更短，这时dist(w) = min(dist(w),dist(u) + c(u,w))。

时间复杂度为O(V^2)(遍历节点-选出最小边-更新所有节点在选入新节点之后最短路变化)

1.2 堆优化的Dijistra算法

上面我们提到的Dijistra算法被称为朴素Dijitra，时间复杂度为O(n^2)，这是因为我们在搜索最小入边的时候将花费O(n)的时间去比较，如何能从一堆数据中快速取得最小值呢？我们可以将待选入的边构成堆的数据结构以方便找到最小值。

• 初始化：将源点的距离设置为0，将其他点的距离设置为无穷大。初始化一个堆，堆里元素存储该点到源点的边权和节点两个数据，将源点加入堆。

• 当堆不为空时，执行以下操作：

  • 弹出堆顶元素u，比较其的边权是否大于已知的最小距离，如果是，则跳过此轮迭代；
  • （松弛）如果否，则遍历u的邻接节点v，如果经过u到v的距离比已知距离小，则更新最短距离dist[v] = dist[u] + w(u,v),并将dist[v]和v入堆。

  import heapq
  
  def dijkstra(graph, start):
      distances = {node: float('inf') for node in graph}
      distances[start] = 0
      queue = [(0, start)]
      
      while queue#每个节点插入，弹出堆:
          current_distance, current_node = heapq.heappop(queue)
          if current_distance > distances[current_node]:
              continue#这一步也叫判重边，原理是实际实现小根堆时，较小的边总是在堆顶，第一次遍历时我们判定它为已经遍历，等到再次遍历时，由于已访问，直接跳过，这实际上是对朴素Dijistra中分离遍历节点和未遍历节点的实现，但是这里我们没有实际实现小根堆，而是通过比较大小将小的边上浮到堆顶，这其实就是实现小根堆，而大的边直接出堆
          for neighbor, weight in graph[current_node].items():#对每条边更新距离
              distance = current_distance + weight
              if distance < distances[neighbor]:
                  distances[neighbor] = distance
                  heapq.heappush(queue, (distance, neighbor))
      
      return distances
  
  # 示例图的邻接表表示
  graph = {
      'A': {'B': 5, 'C': 3},
      'B': {'A': 5, 'C': 2, 'D': 1},
      'C': {'A': 3, 'B': 2, 'D': 6},
      'D': {'B': 1, 'C': 6}
  }
  
  start_node = 'A'
  result = dijkstra(graph, start_node)
  print(result)
  

  将每个节点插入堆的时间复杂度为VlogV，对每条边更新距离的时间复杂度为ElogV，时间复杂度为O((V+E)logV)

  斐波那契堆优化的Dijistra算法

  在上面，我们使用的是二叉堆（优先队列）来优化的Dijistra算法，入堆和出堆操作的期望的时间复杂度为O(log(V))。

  我们也可以用斐波那契堆来优化。

  1. 初始化：将源节点的距离设置为 0，其他节点的距离设置为无穷大。将所有节点加入斐波那契堆中。

  2. 主循环：重复以下步骤，直到斐波那契堆为空。、

     1. a. 从斐波那契堆中提取最小值节点 u。
     2. b. 对于节点 u 的每个邻居节点 v，更新节点 v 的距离为 min(节点 v 的距离, 节点 u 的距离 + 边 (u, v) 的权重)。
     3. c. 如果更新了节点 v 的距离，将节点 v 的距离更新后，将节点 v 的父节点设置为节点 u，并将节点 v 进行级联剪切操作，以维护斐波那契堆的有效性。

  3. 最终结果：当斐波那契堆为空时，所有节点的最短路径已经计算出来，可以根据节点的父节点指针回溯得到最短路径。

  4. 插入节点：向斐波那契堆中插入节点的时间复杂度是 O(1)。

  5. 更新节点距离：更新节点距离时，需要执行级联剪切操作来维护斐波那契堆的有效性。级联剪切操作的时间复杂度是 O(log n)，其中 n 是斐波那契堆中节点的数量。

  6. 提取最小值：提取斐波那契堆中的最小值的时间复杂度是 O(log n)，其中 n 是斐波那契堆中节点的数量。

  综合上述操作，使用斐波那契堆实现 Dijkstra 算法的时间复杂度可以分析如下：

  • 插入节点：O(1)
  • 更新节点距离：O(log n)
  • 提取最小值：O(log n)

  import heapq
  
  class FibonacciHeapNode:
      def __init__(self, key, value):
          self.key = key
          self.value = value
          self.degree = 0
          self.marked = False
          self.parent = None
          self.child = None
          self.left = self
          self.right = self
  
  class FibonacciHeap:
      def __init__(self):
          self.min_node = None
          self.count = 0
  
      def insert(self, key, value):
          new_node = FibonacciHeapNode(key, value)
          if self.min_node:
              new_node.left = self.min_node
              new_node.right = self.min_node.right
              self.min_node.right = new_node
              new_node.right.left = new_node
              if key < self.min_node.key:
                  self.min_node = new_node
          else:
              self.min_node = new_node
          self.count += 1
          return new_node
  
      def merge(self, other_heap):
          if other_heap.min_node:
              if self.min_node:
                  self.min_node.right.left = other_heap.min_node.left
                  other_heap.min_node.left.right = self.min_node.right
                  self.min_node.right = other_heap.min_node
                  other_heap.min_node.left = self.min_node
                  if other_heap.min_node.key < self.min_node.key:
                      self.min_node = other_heap.min_node
              else:
                  self.min_node = other_heap.min_node
              self.count += other_heap.count
  
      def extract_min(self):
          min_node = self.min_node
          if min_node:
              if min_node.child:
                  children = [min_node.child]
                  current = min_node.child.right
                  while current != min_node.child:
                      children.append(current)
                      current = current.right
                  for child in children:
                      child.parent = None
                      child.marked = False
                  self.min_node.left.right = min_node.child
                  min_node.child.left = self.min_node.left
                  self.min_node.left = children[-1]
                  children[-1].right = self.min_node
              min_node.left.right = min_node.right
              min_node.right.left = min_node.left
              if min_node == min_node.right:
                  self.min_node = None
              else:
                  self.min_node = min_node.right
                  self.consolidate()
              self.count -= 1
          return min_node
  
      def consolidate(self):
          max_degree = int(self.count ** 0.5)
          nodes_by_degree = [None] * (max_degree + 1)
          current = self.min_node.right
          while current != self.min_node:
              degree = current.degree
              next_node = current.right
              while nodes_by_degree[degree]:
                  other = nodes_by_degree[degree]
                  if current.key > other.key:
                      current, other = other, current
                  self.link(other, current)
                  nodes_by_degree[degree] = None
                  degree += 1
              nodes_by_degree[degree] = current
              current = next_node
          for node in nodes_by_degree:
              if node:
                  if node.key < self.min_node.key:
                      self.min_node = node
  
      def link(self, child, parent):
          child.left.right = child.right
          child.right.left = child.left
          child.parent = parent
          if parent.child:
              child.left = parent.child
              child.right = parent.child.right
              parent.child.right = child
              child.right.left = child
          else:
              parent.child = child
              child.left = child
              child.right = child
          parent.degree += 1
          child.marked = False
  
  def dijkstra_fibonacci_heap(graph, source):
      n = len(graph)
      dist = [float('inf')] * n
      dist[source] = 0
      visited = [False] * n
  
      fib_heap = FibonacciHeap()
      node_map = {}  # 用于存储顶点和对应的斐波那契堆节点的映射
  
      for i in range(n):
          node = fib_heap.insert(dist[i], i)
          node_map[i] = node
  
      while fib_heap.min_node:
          u = fib_heap.extract_min().value
          visited[u] = True
  
          for v, w in graph[u]:
              if not visited[v] and dist[u] + w < dist[v]:
                  dist[v] = dist[u] + w
                  node = node_map[v]
                  fib_heap.decrease_key(node, dist[v])
  
      return dist
  
  # 测试
  graph = [
      [(1, 4), (7, 8)],
      [(0, 4), (2, 8), (7, 11)],
      [(1, 8), (3, 7), (5, 4), (8, 2)],
      [(2, 7), (4, 9), (5, 14)],
      [(3, 9), (5, 10)],
      [(2, 4), (3, 14), (4, 10), (6, 2)],
      [(5, 2), (7, 1), (8, 6)],
      [(0, 8), (1, 11), (6, 1), (8, 7)],
      [(2, 2), (6, 6), (7, 7)]
  ]
  
  source = 0
  print(dijkstra_fibonacci_heap(graph, source))
  

  在主循环中，对每个节点的邻居节点进行距离更新和级联剪切操作的时间复杂度为 O(d) ，其中 d 是节点的平均度数。

  因此，使用斐波那契堆实现 Dijkstra 算法的总体时间复杂度为 O((|E| + |V|)log |V|)，其中 |E| 是边的数量，|V| 是节点的数量。这是因为在最坏情况下，需要对每个节点进行插入、更新和提取最小值操作，每个操作的时间复杂度为 O(log |V|)，而在主循环中，需要对每条边进行一次距离更新操作，因此总体时间复杂度为 O((|E| + |V|)log |V|)。

  通过比较两者的时间复杂度构成：二叉堆O(VlogV)，斐波那契堆O(|E| + |V|)log |V|))。然而，斐波那契堆的时间复杂度受一个与问题规模无关的常数因子影响，因此实际在稀疏图表现不如二叉堆，在处理规模较大的图上也更有效率。 Bellman算法

2.1 松弛

从S触发，计算邻接结点A，B的最短路估计A.d = 1,B.d = 3，然后根据S->A->B,B.d = A.d + w(A,B) = 1 + 1 =2，显然经过A的最小路径权和更小，因此将最小路径更新为2。

最短路估计是指对于例如B还没有完全搜索到到达B的所有入边，例如最开始的B.d，就是最小边估计，松弛实际上是在更新最小路估计。

下面的伪代码是基于E(u,v)进行松弛操作，用来更新v对应的 s⇝v 的预估值v.d。w(u,v)对应的是E(u,v)的权值。另外‘v.pi 同 v.Π

 RELAX(u,v,w)
  if v.d > u.d + w(u,v)
   v.d = u.d + w(u,v)
   v.pi = u

2.2 Belman算法

 BELLMAN-FORD(G,w,s)
  INITIALIZE-SIGNAL-SOURCE(G,s)
   for i=1 to |G.V|-1
     for each edge(u,v) in G.E
       RELAX(u,v,w)
   for each edge(u,v) in G.E
    if v.d > u.d + w(u,v)
     return FALSE
  return TRUE

第一个for循环对所有边执行V-1次松弛操作，为什么对所有边进行排查，因为我们要对一个节点所有可能连接的边进行排查（未邻接的点的边被初始化负无穷，在更新过程肯定被优化），确保不会有新的边的加入使得最短路发生变化，为什么执行V-1次，因为一共有V- 1个节点（除s）。每执行一次松弛操作，都能确定一个节点的最短路径。

第二个for循环检查是否有负权环，有负权环的话，在经历V-1次松弛后，最短路估计仍能被更新。

时间复杂度为O(VE)。

松弛收敛

在更新最短路估计的过程中，最短路估计会不断被更新为更小的值，这个值是有上界的，到达上界之后，便不再改变，这点叫做收敛性质，表示为：
$$v.d>=\delta (s,v),\delta (s,v)为s到v的最小路估计的上界$$
这一点表明Bellman算法是能被优化的，不需要完全执行到V-1次

为什么负权环不能处理

实际上，在第一次松弛处理，X的前驱节点一定为s，即便环中权为正（很容易得到），它遵守收敛性质，x的最小路估计已经到达下界不再被更新，但在图中我们能知道它在此后也被更新了。这是因为第一次松弛处理时，由于环中负权的存在，x.d被更新为T.d + w(T,X),前驱节点v.p也被更新为T，此时x和s的已经断了，从这个角度，即便算法结束，不能够通过这条路径到达s。另外，由于负权环的存在，x.d的值会被不断更新，因为T.d + w(T,x)中，由于上次松弛的X.d变得更小,使得T.d在此轮松弛中变得更小,x.d将被更新为T.d + w(T,X)，不断变小。

我们可以利用这一点反推是否存在负权环，因为对于不存在负权环的图来说，只需要进行V-1次松弛，如果第V次松弛仍然可以更新最小路估计，那么这个图存在负权环。

实际上，Dijistra也是松弛法，最短路的研究是对松弛法松弛的顺序的研究，比如Dijistra法通过将搜索过的节点和未搜索过的节点分开，将未搜索过的节点逐渐加入搜过的节点的集合来确定顺序。

3. SPFA算法(队列优化的Bellman算法)

二. 多源最短路径

1. Floyed算法

多源最短路问题要求我们求每一对节点之间的距离，我们可以将其转化成一个动态规划问题。

譬如我需要求节点5到节点7的最短路，我们可以将其转换为求节点5到其他任意节点，再从其他任意节点到节点7的最短路，因而我们得到了状态转移方程：
$$dist[5][7]=min(dist[5][i]+dist[i,7]foriinrange(n))$$
因此，对于任意对节点的最小路，我们可以用另外两个参树来控制遍历：

for i in range(n):
	for j in range(n):
		for k in range(n):
			dist[j][k] = min(dist[j][i],dist[i][k])

dp表上的dp值就代表了这一点的最短路权和，如果要记录路径上的点，定义一个数据结构（比如vector），每次状态转移条件满足时，将满足条件转移的k值加入数据结构即可。

时间复杂度为O(n^3)。

2. Johnson算法

在说明Johnson算法前回顾一下什么是邻接表和邻接矩阵。

• 邻接表是一种基于链表的数据结构，它使用链表来表示图中每个顶点的邻居节点。对于稀疏图来说，邻接表可以节省空间，因为它只存储有边相连的顶点。但是在查找某个顶点的邻居节点时，需要遍历链表，所以在查找邻居节点的操作上效率较低。

• 邻接矩阵是一种基于二维数组的数据结构，它使用二维数组来表示图中每个顶点之间的连接关系。对于稠密图来说，邻接矩阵可以更加高效地表示图的连接关系，因为它可以直接通过数组索引来查找顶点之间的连接关系。但是在稀疏图中，邻接矩阵可能会浪费大量的空间，因为它需要存储所有顶点之间的连接关系。

综上所述，邻接表适合表示稀疏图，而邻接矩阵适合表示稠密图。

举个例子：

假设有一个无向图，其中包含4个顶点和3条边，边的连接关系如下：

顶点1和顶点2相连 顶点2和顶点3相连 顶点3和顶点4相连

邻接表表示： 顶点1：2 顶点2：1, 3 顶点3：2, 4 顶点4：3

邻接矩阵表示：

   1  2  3  4
1  0  1  0  0
2  1  0  1  0
3  0  1  0  1
4  0  0  1  0

本Johnson算法就是针对稀疏图和使用邻接表表示图而言有优势的算法。

Johnson算法是对Heap优化的Dijistra算法的改良，由于Dijistra法并不能解决负权环问题，因此Johnson的关键技术在于建非负权并与原边权映射。

Johnson算法利用Bellman算法可判负环的性质，由松弛的过程得
$$h(v)<=h(u)+w(u,v)$$
那么可以知道：
$$w(u,v)+h(u)-h(v)>=0$$
我们就令左边部分为新边权：
$$w^{\prime }(u,v)=w(u,v)+h(u)-h(v)>=0$$
新边权非负是恒成立的。

假设此时我要求这样一个路径，求路径和

我们得到了原边权和和新边权和的映射关系，它适用与最短路的边权计算。

因此我们可以整理一下，得到了Johnson算法。

• 建立一个虚拟源点o，o与所有节点邻接，从源点o到各个节点的边权为0;
• Bellman算法（SPFA）求源点o到各节点的单源最短路径，对任意点v的最短路为h(v);
• 根据w’(u,v) = w(u,v) + h(u) -h(v)>=0，建立新边权w’(u,v)；
• 以每个节点为源点，执行V（节点数）轮Heap-Dijistra算法。

对于稀疏图，二叉堆优化的Dijistra算法效率更好(O(VElgV))，对于稠密图而言，用斐波那契堆O(V^2lgV+VE）优化更好。