作为一个NOIP(现在好像叫CSP来着)的普及组菜鸡,

终于决定来写一篇关于图论的文章

比较教会了别人自己就会了嘛

(虽然我自己好像也不是怎么的样子)

Floyd算法

Floyd算法
就是暴力朴素地用循环列举出起点、终点、以及起点和终点之间的点
通过比较直接距离与间接距离(就是起点到一个点,那个点再到终点的距离)
求出图上任意一点到另一点的距离。。。
太菜说不清 还是直接上代码吧

int n,m;
cin >> n >> m;
memset(f,0x3f,sizeof(f));
for(int i = 1;i <= n;i++)
    f[i][i] = 0;
for(int i = 1;i <= m;i++)
{
    int x,y,w;
    cin >> x >> y >>w;
    f[x][y] = w;
}
for(int k = 1;k <= n;k++)
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            f[i][j] = min(f[i][j],f[i][k] + f[k][j]);

拆分解释。。。。

int n,m;
cin >> n >> m;

首先图里有n个点,m条边
定义n,m读取n,m的大小

memset(f,0x3f,sizeof(f));

首先初始化f数组(我没定义,记得先定义)
f数组是一个二维数组,用于存储点到点的距离(我用的邻接矩阵,
f[i][j] 就是图中点i到点j的距离
0x3f 等价于 0x3f3f3f3f 反正是个很大的数(这里看做无限大)就是点i到点j没有直接相连的边

for(int i = 1;i <= n;i++)
    f[i][i] = 0;

在图中点i到自身的距离肯定是0对吧

for(int i = 1;i <= m;i++)
{
    int x,y,w;
    cin >> x >> y >>w;
    f[x][y] = w;
}

读取边(起点x,终点y,连接x,y的边的权值)
并储存到f数组中

for(int k = 1;k <= n;k++)
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            f[i][j] = min(f[i][j],f[i][k] + f[k][j]);

首先外围的第一个for循环用于枚举点k(反正就是起点和终点直接的那个点)
接下来一个双重循环用于枚举起点和终点
==接下来是重点==
比较f[i][j] 目前存储的最短距离 和 点i到点k,再从点k到点j(点i到点j通过点k中转的距离),看看谁小,如果通过点k中转的距离短,就更新f[i][j]中的取值,如此循环


这样当循环结束的时候,f数组里面存储的就是任意一点到另一点的最短距离的
需要输出点i到点j的最短距离只需输出 f[i][j]就行了


可我们会发现一个问题,当点的数量为n时,时间复杂度就是O(nnn*),遇到稍微大一点的数据肯定就会超时的,所以接下来要请出Dijkstra

Dijkstra算法

Dijsktra算法可以说基于贪心的思想,从每步最优到整体最优
首先枚举从点1到其他点的距离,找到离点1最近的那个边
接着枚举点2。。。以此类推,找到原点到其他点的最短距离
啊啊啊啊,反正我也说不清,直接上代码

    cin >> n >> m >> s;
    memset(f,0x3f,sizeof(f));
    for(int i = 1;i <= n;i++)
        f[i][i] = 0;
    for(int i = 1;i <= m;i++){
        int x,y,w;
        cin >> x >> y >> w;
        f[x][y] = min(f[x][y],w);
    }
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    for(int i = 1;i <= n;i++)
        dis[s] = f[s][i];
    dis[s] = 0;
    vis[s] = true;
    for(int i = 1;i <= n;i++){
        int minans = 0x3f3f3f3f;
        for(int j = 1;j <= n;j++)
            if(!vis[j] && dis[j] < minans){
                minans = dis[j];
                u = j;
            }
        vis[u] = true;
        for(int v = 1;v <= n;v++)
            dis[v] = min(dis[v],dis[u] + f[u][v]);
    }

仍然拆分解释(我觉得写注释说不清楚)

    cin >> n >> m >> s;
    memset(f,0x3f,sizeof(f));
    for(int i = 1;i <= n;i++)
        f[i][i] = 0;
    for(int i = 1;i <= m;i++){
        int x,y,w;
        cin >> x >> y >> w;
        f[x][y] = min(f[x][y],w);
    }
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));

首先仍然是熟悉的初始化(好像有些变动)
首先新增了原点s,因为Dijkstra适用于单源最短路,就是输入图,输出从原点s,到其他点的最短距离
这里在读取的时候我加上了对重边的改动(就是当一点到另一点有两条及以上的边相连是,取最短的那条作为距离)
然后我们又引入了dis数组和vis数组
dis数组用于记录原点s到其他点的最短距离(f数组只用于储存图,不用于记录最短路了)
vis用于标记已访问的点,防止重复,下面会用到

for(int i = 1;i <= n;i++)
        dis[s] = f[s][i];
    dis[s] = 0;
    vis[s] = true;

这段依然属于初始化
首先用循环,先向dis数组里写入最初图中与原点s直接相连的点到原点的距离(不直接相连的当然是0x3f,反正就看做是无限大了
然后dis[s]的话,自己到自己肯定是0了,这句不写其实不要紧,上面f[s][s]的值是0
然后标记vis[s] = false,原点s已访问,当然~。

for(int i = 1;i < n;i++){
        int minans = 0x3f3f3f3f;
        for(int j = 1;j <= n;j++)
            if(!vis[j] && dis[j] < minans){
                minans = dis[j];
                u = j;
            }
        vis[u] = true;
        for(int v = 1;v <= n;v++)
            dis[v] = min(dis[v],dis[u] + f[u][v]);
    }

==这段就是最主要的核心代码了==
首先for循环枚举图上的每一个点i
首先定义一个最小距离minans的值为0x3f3f3f3f,也看做无限大了
接下来枚举点j
如果点j没有被访问过,且原点到点j的距离是最短的,将minansh更新成dis[j]
且用u记录下点j
循环结束后就能找到最近的那个点
标记点u已被访问
然后枚举点v
比较原点到点u的最短距离dis[s] 和 原点到点u的距离(也就是最短距离) 加上 点u到点v的直接距离
如果后者小就更新
连续n - 1个循环后 dis数组里面储存的就是原点到每个点的最短距离了


说实话我对Dijkstra真的不是特别懂,可能讲解有误。。。这真的没办法惹


PS:其实Dijkstra还有更高级的用法,用Dijkstra加上堆优化,只要维护堆,就可以从堆顶取得最近的点,无需循环,这样效率会很高,甚至会超过下面的Bellman和SPFA(但我其实不会写
PSS:Dijkstra的用途其实也非常多,甚至TCP/IP里面底层 在网络上查找最短路就是用Dijkstra算法实现的。。。。。

???啥,你问我SPFA在哪?

。。。没时间写惹,自己百度去吧!!!


Maybe Some Days are Rainy,But My Heart is Luciferous!