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

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

废话不多说我们先上图

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

时间复杂度如何使用？

C++ 一秒钟大概计算1000万次,我们将迭代次数n带入O()中,计算大概多少

Dijkstra 时间复杂度 O（n^2） 稠密图

思路:

• 初始化dist = 0x3f 并且 dis[1] = 0
• 迭代n次
• 找到没有被更新过的最近距离的点
• 用这个点更新其他点 并且给这个点打上标记

代码:

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i m>>k;
    for(int i=1; ia>>b>>c;
        d[a][b] = min(d[a][b],c);
    }
FLOYD
    for(int k1=1; k1