Dijkstra算法

Dijkstra算法是一种最短路径路由算法,用于求单源最短路径，但其要求边权不能为负值。
bellman-ford算法也是用来去单源最短路径，但是其边权可以负值。
spfa算法为bellman-ford的算法的优化版本，在有些情况下能够实现较小的时间复杂度。
核心实现部分。
Dijkstra:利用贪心的思想，每次加入最近的未访问节点，从而得到最短路径。

int dijkstra() {
    //所有节点距离起点的距离初始化为无穷大
    for(int i=1;i<=n;i++)
    {
        dist[i] = inf;
    }
    //起点距离自己的距离为零
    dist[1] = 0;

    //迭代n次，每次可以确定一个点到起点的最短路
    for (int i = 0; i < n; ++i) {
        int t = -1;
        //t的作用？
        for (int j = 1; j <= n; ++j) {
            //不在s集合，并且
            //如果没有更新过，则进行更新， 或者发现更短的路径，则进行更新
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }

        //加入到s集合中
        st[t] = true;

        //找到了距离最小的点t，并用最小的点t去更新其他的点到起点的距离
        for (int j = 1; j <= n; ++j) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }

    // 如果起点到达不了n号节点，则返回-1
    if (dist[n] == inf) return -1;
    // 返回起点距离n号节点的最短距离
    return dist[n];
}

Dijkstra 还可以进行堆优化，可使用STL优先队列。
从O(n2)优化为O(nlogn)

int dijstrkual()
{
    dist[1] =0;
    pq.push({0,1});
    while(!pq.empty())
    {
        auto t = pq.top();
        pq.pop();
        int distance = t.first;
        int u = t.second;
        if(vis[u])continue;
        else vis[u] = true;
        for(auto&v:gra[u])
        {
            int y = v.first;
            int d = v.second;
            if(dist[y]>distance+d)
            {
                dist[y] = distance+d;
                pq.push({dist[y],y});
            }
        }
    }
    return dist[n];
}

bellman-ford:循环遍历图中的所有边，对图中的边进行松弛操作，从而得到可能的最短路径。

int bellman_ford()
{
    dist[1]=0;
    for(int i=0;i<k;i++)//第次i松弛操作保证了所有深度为i的路径最短
    {
        vector<int>last = dist;
        for(int j=0;j<=m;j++)
        {
            int a = edges[j][0];
            int b = edges[j][1];
            int w = edges[j][2];
            dist[b] = min(dist[b],last[a]+w);//保证每次只更新一次，防止串联
        }
    }
    return dist[n];
    
}

spfa：SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，它的优化思路是利用了搜索的思想，只将对更新了距离的节点加入队列，因为只有更新了距离的节点才对后续的松弛操作有影响。
优化方式：

int spfa()
{
    queue<int>q;
    q.push(1);
    dist[1]=0;
    vis[1]=true;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u]=false;
        for(auto&vp:gra[u])
        {
            int v = vp.first;
            int d = vp.second;
            if(dist[v]>dist[u]+d)
            {
                dist[v] = dist[u]+d;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v] =true;
                }
            }
        }
    }
    return dist[n];
}

和Dijkstra很像，但Dijkstra是贪心，每次更新一点，而spfa是对所有的边都进行松弛。
spfa还可以进行判断负环操作。

bool spfa()//整体思路，dist代表到超级源点的距离。
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        q.push(i);
    }
    while(!q.empty())
    {
        int u= q.front();
        q.pop();
        vis[u] =false;
        for(auto&vp:gra[u])
        {
            int v = vp.first;
            int d = vp.second;
            if(dist[v]>dist[u]+d)
            {
                dist[v] =dist[u]+d;
                cnt[v] = cnt[u]+1;
                if(cnt[v]>=n) return true;//抽屉原理，边数超过了点数。存在负环。
                if(!vis[v])
                {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    return false;
}

Floyd算法可以用来解决多源最短路径问题，它的思想基于动态规划。
从点i到点j的最短路径，要么由i直接到j，要么是由i经过点k再到达点j。点i到点j的最小值只能从这两种状态转移过来，从而建立动态规划转移方程。

void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                d[i][j] =min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}