Single-source shortest paths problem

Overview

• DFS和BFS无法直接适用于最短路径问题
  • 由于dynamic range of the weights？
    • 最短路径可以被理解为动态规划问题，而动态规划问题复杂度往往与数值本身成正相关，比如说背包问题，复杂度与背包大小正相关
  • 最短路径问题的难点在于：随着节点增加，路径数量指数上升
• Dijkstra $O(VlgV+E)$ Bellman Ford $O(VE)$
  • 算法复杂度与权重无关，只与VE有关
  • 通常$E = O(V^2)$ （$1+2+3+....+N=N^2$)
  • Dijkstra 只能处理正权重，Bellman Ford能处理负权重，更加普适，但也更加慢

Negative-Weights Edges

• 为什么有负权重

社交网络：喜欢/不喜欢

<aside> 💡 在处理问题时，可以先思考是否够存在一种方式shifting weights to make them all positive，这样就可以用Dijkstra，而不用Bellman Ford了

</aside>

• negative cycles

从Source S到B的最小权重是-inf 所以朴素的办法似乎找不到一个最短路径

负循环会让最短路径难以定义

复杂度

随着节点增加，复杂度指数上升

解决S.P.的框架(no negetive cycles)

Relax edge(u,v) : 即检查此条边是否能让u到v的路径变短

其中

• S Source 假设是单一的 Single Source Shortest Paths