第一种: dij算法
基于贪心思想
dij算法的逻辑是:最短的距离不可能再被其他点更新 因此可以拿这个点来更新其他点
vis[x]表示这个点是否被拓展过 每个点只会被拓展一次
第二种: spfa算法
基于bfs思想
逻辑是:如果所有的点都满足\(d[y]<=d[x]+z\) 那么最短路就成立了 所以不断更新直到没有办法在更新为止
加上队列优化 每次只有被更新的点才有个能进一步被更新
会进行多次三角不等式的判断
2024-04-07 13:51:50
第一种: dij算法
基于贪心思想
dij算法的逻辑是:最短的距离不可能再被其他点更新 因此可以拿这个点来更新其他点
vis[x]表示这个点是否被拓展过 每个点只会被拓展一次
第二种: spfa算法
基于bfs思想
逻辑是:如果所有的点都满足\(d[y]<=d[x]+z\) 那么最短路就成立了 所以不断更新直到没有办法在更新为止
加上队列优化 每次只有被更新的点才有个能进一步被更新
会进行多次三角不等式的判断