[算法总结] 最短路算法归纳2 --不会详讲 适合还不怎么会的新手!

>>>>本篇博客希望帮助你们更好的记忆模板,如果需要深刻理解还需日后的刷题巩固>>>>>

废话不多说我们先上图

[图片来源于]https://www.acwing.com/blog/content/140/ 如侵必删

Bellman-ford(spfa的前置技能—目前对我来说很少用)

具体思路:

• 迭代n次
• 循环所有边 a b w 存在一条从a走向b的边 权重w
• dist[b] = min(dis[b],dist[a]+w) 松弛操作
• 从而 所有的边都 dist[b]=n也就是从1~x至少经过了n条边 所以至少经过了n+1个点

  代码如下:

  bool spfa()
  {
      queue q;
  
      for (int i = 1; i  dist[t] + w[i])
              {
                  dist[j] = dist[t] + w[i];
                  cnt[j] = cnt[t] + 1;
  
                  if (cnt[j] >= n) return true;
                  if (!st[j])
                  {
                      q.push(j);
                      st[j] = true;
                  }
              }
          }
      }
  
      return false;
  }