学步园

前面说过dijkstra不能对负权边进行操作，而现在介绍的SPFA算法是对dijkstra的一种改进，它可以对负权边进行处理，而且还可以判断是否存在负环。

如果存在一个点进入队列的次数超过N次，则存在负环。

下面SPFA的代码可以代替dijkstra的代码：

int SPFA(int star, int end, int n)
{
    dis[star] = 0;
    Q.push(star);
    used[star] = true;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        used[u] = false;
        for (int v = 0; v < n; v++)
        {
            if (map[u][v] != INF && dis[u] + map[u][v] < dis[v])        //松弛操作
              {
                dis[v] = dis[u] + map[u][v];
                if (!used[v])
                {
                    used[v] = true;
                    Q.push(v);
                }
            }
        }
    }
    return dis[end];
}

下面是HDOJ-1874用SPFA改写的代码：

#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 200 + 10;
int map[MAXN][MAXN];
int dis[MAXN];        //保存所有点到起点的最小距离
bool used[MAXN];
const INF = 0x3ffffff;
queue <int > Q;

void init(int n)
{
    for (int i = 0; i < n; i++)
    {
        dis[i] = INF;
        for (int j = 0; j < n; j++)
        {
            map[i][j] = INF;
        }
    }
    memset (used,false,sizeof(used));
    while (!Q.empty())
    {
        Q.pop();
    }
}

int SPFA(int star, int end, int n)
{
    dis[star] = 0;
    Q.push(star);
    used[star] = true;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        used[u] = false;
        for (int v = 0; v < n; v++)
        {
            if (map[u][v] != INF && dis[u] + map[u][v] < dis[v])        //松弛操作
            {
                dis[v] = dis[u] + map[u][v];
                if (!used[v])
                {
                    used[v] = true;
                    Q.push(v);
                }
            }
        }
    }
    if (dis[end] == INF)
    {
        return -1;
    }
    else
    {
        return dis[end];
    }
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int a,b,c;
        init(n);
        for (int i = 0; i < m; i++)
        {
            cin>>a>>b>>c;
            if(c < map[a][b])        //考虑如果有重边，用最小的进行构造图(好坑爹啊！！)
            {
                map[a][b] = c;
                map[b][a] = c;
            }
        }
        int s,t;
        cin>>s>>t;
        cout<<SPFA(s, t, n)<<endl;
    }
    return 0;
}