图论_最短路_spfa.cpp

一些ACM基本算法的测试源码

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

const int SIZE = 1001;
const int INF = 1000000000;

int n;
int dist[SIZE], num[SIZE], queue[100 * SIZE];
bool visit[SIZE];//顶点是否在队列中 

struct Edge{
    int to, w;  
    Edge(int tto, int tw) : to(tto), w(tw) {}     
};

vector<Edge>edge[SIZE];
//顶点从0开始 
bool SPFA()
{
    int i, k, curs, head = 0, tail = 0;
    for(i = 0; i < n; i ++)
    {
        queue[tail ++] = i;
        visit[i] = true;
        dist[i] = INF; 
        num[i] = 1;     
    }         
    dist[0] = 0;
    while(head < tail)
    {
        k = queue[head ++];
        curs = edge[k].size();
        for(i = 0; i < curs; i ++)
        {
            if(dist[edge[k][i].to] > dist[k] + edge[k][i].w)
            {
                dist[edge[k][i].to] = dist[k] + edge[k][i].w;
                if(!visit[edge[k][i].to])
                {
                    queue[tail ++] = edge[k][i].to;
                    num[edge[k][i].to] ++; 
                    if(num[edge[k][i].to] > n)  return false;//如果某个点进入队列的次数超过N次则存在负环
                    visit[edge[k][i].to] = true;
                }
            }
        }
        visit[k] = false;               
    }
    return true;
}

int main()
{
    int e,u, v, w;
    scanf("%d%d", &n, &e);
    for(int i = 0; i < e; i ++)
    {
        scanf("%d%d%d", &u, &v, &w);
        edge[u].push_back(Edge(v, w));   
        //edge[v].push(Edge(u, w)); 无向图        
    }    
    if(SPFA())
    {
        for(int i = 0; i < n; i ++)
            printf("%d\n", dist[i]);
    }
    else  printf("存在负环!\n");
    system("pause");
    return 0;       
}