最短路的三种算法

第一种: dij算法
基于贪心思想
dij算法的逻辑是:最短的距离不可能再被其他点更新 因此可以拿这个点来更新其他点
vis[x]表示这个点是否被拓展过 每个点只会被拓展一次

第二种: spfa算法
基于bfs思想
逻辑是:如果所有的点都满足\(d[y]<=d[x]+z\) 那么最短路就成立了 所以不断更新直到没有办法在更新为止
加上队列优化 每次只有被更新的点才有个能进一步被更新
会进行多次三角不等式的判断

上一篇:【日报#364】基数堆和Dij


下一篇:图论:dij算法优化:双端队列及详细证明