最短路

Dijkstra算法

朴素的Dijkstra算法和prim算法在代码上惊人的相似。

而Dijkstra算法的思想是：在待扩展边中取出最小边，利用此边进行松弛操作，然后更新待扩展边集。重复以上步骤直到所有结点都已访问过。

Dijkstra算法只对没有负权回路的图有效，当然对带负权边，但没有负权回路的图依然有效。

for (int i=1;i<n;i++)
{
    minn=INF;
    for (int j=1;j<=n;j++)
    if (!vis[j] && d[j]<minn)
        minn=d[k=j];
    vis[k]=true;
    for (int j=1;j<=n;j++)
        d[j]=min(d[j],d[k]+map[k][j]);
}

明显朴素的Dijkstra算法耗时O(N^2)，时间主要浪费在每次循环寻找待扩展边中的最小边，利用C++的STL提供的方便，使用优先队列进行优化，当然图的存储方法只能改为使用边表存储，否则松弛操作一样耗时巨大。下面的代码写得一般，有点长了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

struct edge{     //存储边
    int v,w;
    edge() { v=w=0; }
    edge(int x,int y) { v=x; w=y; }
};
vector<edge> a[100];

struct node{         //存储待扩展边的数据，当然也可以直接利用存储边的结构体，但是为了直观就分开写了
    int dd,w;     //dd存储结点，w存储边权
    node() {dd=w=0; };
    node(int x,int y) { dd=x;w=y; }
    bool operator < (const node &x) const      //优先队列比较函数
    {
        if (w==x.w) return dd<x.dd;
        else return w<x.w;
    }
};

int d[100];
int dis[100];

void dijkstra(int S)
{
    priority_queue<node> p;
    memset(dis,10,sizeof(dis));
    dis[S]=0;
    p.push(node(S,dis[S]));     //把start点压入队列
    while (!p.empty())
    {
        node u=p.top(); p.pop();    //弹出待扩展边的最小边
        for (int i=0;i<d[u.dd];i++)    //松弛操作
        {
            edge e=a[u.dd][i];
            if (dis[e.v]>u.w+e.w)
            {
                dis[e.v]=u.w+e.w;
                p.push(node(e.v,dis[e.v]));  //待扩展边进队
            }
        }
    }
}

int main()
{
    for (int i=0;i<100;i++) a[i].clear();
    memset(d,0,sizeof(d));

    int n,m,u,v,w;
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        a[u].push_back(edge(v,w));
        d[u]++;
    }

    dijkstra(1);

    for (int i=1;i<=n;i++)
        cout<<"1->"<<i<<":"<<dis[i]<<endl;
    return 0;
}

Bellman-Ford算法

朴素的bellman-ford算法说死了就是一个笨方法，就是通过不断地对每一条边进行松弛操作，耗时O(VE)，但是经过一个简单的优化后效率大大提升，听说效率比Dijkstra好多了。

这里直接给出经过优化的bellman-ford算法。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define NN 105

struct edge{
    int u,v,w;
    edge() {u=v=w=0;}
    edge(int x,int y,int z) {u=x;v=y;w=z;}
};

vector <edge> e;
int n;
int dis[NN];

bool relax(int u,int v,int w)  //松弛操作
{
    if (dis[u]+w<dis[v])
    {
        dis[v]=dis[u]+w;
        return true;
    }
    return false;
}

bool Bell(int S)
{
    memset(dis,10,sizeof(dis));
    dis[S]=0;

    bool flag=false;
    int count=0;
    while (!flag && ++count<n)  //注意flag的变化，其实flag就是优化，不用flag则运行n-1次也会停下来
    {
        for (int i=0;i<e.size();i++)
            flag=flag||relax(e[i].u,e[i].v,e[i].w);  //如果没有进行过松弛操作，那么就没必要在做下去了
        flag=!flag;
    }

    for (int i=0;i<e.size();i++)   //负权回路的判断
        if (relax(e[i].u,e[i].v,e[i].w))
            return false;
    return true;
}

int main()
{
    int m,u,v,w;
    cin>>n>>m;
    e.clear();
    for (int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        e.push_back(edge(u,v,w));
        e.push_back(edge(v,u,w));
    }

    bool ff=Bell(1);
    if (!ff)
        cout<<"no"<<endl;
    else for (int i=2;i<=n;i++)
            cout<<dis[i]<<endl;
    return 0;
}

SPFA算法

SPFA算法是西南交大段凡丁发表的，在bellman-ford的基础上加入了队列优化，而在SPFA算法上又可以加入SLF和LLL优化，使得整个算法的效率非常可观。

算法的思想是从队列中取出点进行松弛操作，若松弛成功则加入队列，直到队列为空。而为了处理负权回路，需要加入一个数组记录结点入队的次数，若一个结点入队次数大于n，则可以判断出现了负权回路。

这里并没有加入SLF和LLL优化。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

#define NN 1000

struct edge{
    int v,w;
    edge() {v=w=0;}
    edge(int x,int y) {v=x;w=y;}
};

vector<edge> e[NN];
int dis[NN];
int n;

bool relax(int u,int v,int w)    //松弛操作
{
    if (dis[u]+w<dis[v])
    {
        dis[v]=dis[u]+w;
        return true;
    }
    return false;
}

bool SPFA(int S)
{
    memset(dis,10,sizeof(dis));
    dis[S]=0;

    int count[NN]={0};    //统计入队次数
    count[S]=1;

    queue<int> q;
    q.push(S);

    bool f[NN]={0};    //标记是否在队列中，避免重复进队
    f[S]=true;
    while (!q.empty())
    {
        int u=q.front();
        for (int i=0;i<e[u].size();i++)
        {
            int v=e[u][i].v;
            if (count[v]>=n) return false;
            if (!f[v] && relax(u,v,e[u][i].w))
            {
                count[v]++;
                q.push(v);
                f[v]=true;
            }
        }
        q.pop();
        f[u]=false;
    }
    return true;
}

int main()
{
    int m,u,v,w;
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        e[u].push_back(edge(v,w));
        e[v].push_back(edge(u,w));  //无向图
    }

    bool ff=SPFA(1);

    if (!ff) cout<<"no"<<endl;
    else for (int i=2;i<=n;i++)
            cout<<dis[i]<<endl;
    return 0;
}

Floyd算法

Floyd算法最简单但是速度不敢恭维。

思想：对每个节点不断进行松弛操作，到最后得到的结果就是多源最短路的结果了。

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