[图论]最短路

Dijkstra-Heap

说明

Dijkstra-Heap使用优先队列，比Dijkstra快一点

使用方法

1. Dijkstra d;
2. d.init(n); 顶点为n
3. d.adde(x,y,w);加边
4. cout<<d.get_ans(int source,int destination)<<endl;输出最短路的值

模板

const int maxn=100000+5; //最大顶点数
const int INF=0x3f3f3f3f;
using namespace std;
struct Edge
{
    int from,to, dist;
    Edge(int u,int v,int d):from(u),to(v),dist(d){}
};
struct HeapNode
{
    int d,u;
    bool operator < (const HeapNode& rhs)const
    {
        return d>rhs.d;
    }
};
struct Dijkstra
{
    int n,m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool done[maxn];    //是否已永久标号
    int d[maxn];        //s(源点)到各个点的距离
    int p[maxn];        //最短路中的上一条弧
    void init(int n)
    {
        this->n=n;
        for(int i=0;i<=n;i++)    G[i].clear();
        edges.clear();
    }

    void adde(int from,int to,int dist)
    {
        edges.push_back(Edge(from-1, to-1, dist));
        m=edges.size();
        G[from-1].push_back(m-1);
    }

    void dijkstra(int s)
    {
        priority_queue<HeapNode> q;
        for(int i=0;i<n;i++)    d[i]=INF;
        d[s]=0;
        memset(done, 0, sizeof(done));
        q.push((HeapNode){0,s});
        while(!q.empty())
        {
            HeapNode x=q.top();q.pop();
            int u=x.u;
            if(done[u])    continue;
            done[u]=true;
            for(int i=0;i<G[u].size();i++)
            {
                Edge& e=edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist)
                {
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
    }

    int get_ans(int source,int destination)
    {
        dijkstra(source-1);
        return d[destination-1];
    }
};

SPFA

说明

1. SPFA是Bellman-Ford的进化版
2. SPFA在网络流中也有应用
3. 可以用于判环，同样可以判环的还有拓扑排序

使用方法

确定点边的最大数量 Vmax Emax

init()

adde(x,y,w);adde(y,x,w);双向加边

cout<<get_ans(int n,int source,int destination)<<endl; n个点、起点、终点

模板

const int INF=0x3f3f3f3f;
typedef int mytype;
const int Vmax=500+10;
const int Emax=1000+10;//未翻倍时
int he[Vmax],ecnt;
struct edge
{
    int v,next;
    mytype w;
}e[Emax*2];
int dis[Vmax];
int vcnt[Vmax]; //记录每个点进队次数，用于判断是否出现负环
bool inq[Vmax];
int pre[Vmax]; //记录最短路中的上一个节点

void init()
{
    ecnt=0;
    memset(he,-1,sizeof(he));
    // SPFA初始化
    memset(inq,false,sizeof(inq));
    memset(vcnt,0,sizeof(vcnt));
    memset(dis,INF,sizeof(dis));
}

void adde(int from,int to,mytype w)
{
    e[ecnt].v=to;
    e[ecnt].w=w;
    e[ecnt].next=he[from];
    he[from]=ecnt++;
}

bool SPFA(int n,int source)
{//n为顶点数 source为起点
    //return true表示无负环，反之亦然
    dis[source]=0;
    queue<int>q;
    q.push(source);inq[source]=true;
    while (!q.empty())
    {
        int tmp=q.front();
        q.pop();inq[tmp]=false;
        //判断负环
        vcnt[tmp]++;
        if (vcnt[tmp]>=n) return false;
        for (int i=he[tmp]; i!=-1; i=e[i].next)
        {
            int w=e[i].w;
            int v=e[i].v;
            if (dis[tmp]+w<dis[v])
            {
                dis[v]=dis[tmp]+w; //松弛操作
                pre[v]=tmp;
                if (!inq[v])
                {
                    q.push(v);
                    inq[v]=true;
                }
            }
        }
    }
    return true;
}

mytype get_ans(int n,int source,int destination)
{
    SPFA(n,source);
    return dis[destination];
}