图论模板

Dijkstra普通版实现

const int INF = ~0U >> 2;   //代表无穷大
const int VN = 100;        //最大顶点数
void Dijkstra(int s,int n)//s代表起点，n代表顶点个数
{
    bool vst[VN];
    memset(vst,0,sizeof(vst));
    for(int i = 1;i <= n;++i) d[i] = (i==s?0:INF);
    int kase = n; 
    while(kase--)
    {
        int x,m = INF;
        for(int y = 1;y <= n;++y) 
          if(!vst[y]&&d[y] <= m) m = d[x=y];
        vst[x] = 1;
        for(int y = 1;y <= n;++y)
        {
            if(d[y] > d[x]+w[x][y]) //松弛操作
            {
                d[y] = d[x] + w[x][y]; 
            }
        }
    }
}

除了求出最短路的长度外，使用Dijkstra算法也能很方便
地打印出从起点结点到所有结点的最短路，原理和动态规划中
的方案一样——从终点出发，不断顺着d[i]+w[i][j] = d[j]的边
（i,j）从结点j“退回”到结点i，直到回到起点。另外，仍然
可以用空间换时间，在更新d数组时维护“父亲指针”。
if(d[y] > d[x]+w[x][y])
{
d[y] = d[x]+w[x][y];
fa[y] = x;
}

Dijkstra优先队列加邻接表实现

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

typedef pair<int,int>pii;
const int INF = ~0U >> 2;
const int VN = 100;
int d[VN];
int top,w[2*VN],Head[VN],Key[2*VN],Next[2*VN];
void Add(int u,int v,int cost)
{
    w[top] = cost;
    Key[top] = v;
    Next[top] = Head[u];
    Head[u] = top++;
}
void Dijkstra(int s,int n)            //s代表起点，n代表顶点数
{
    priority_queue<pii,vector<pii>,greater<pii> > q;
    for(int i = 1;i <= n;++i) d[i] = (i==s?0:INF);
    q.push(make_pair(d[s],s));        //起点进入优先队列
    while(!q.empty())
    {
        pii u = q.top();
        q.pop();
        int x = u.second;   cout<<"x = "<<u.second<<" d = "<<d[x]<<endl;
        if(u.first != d[x])continue;  //已经算过，忽略
        for(int e = Head[x];e != -1;e = Next[e])
        {        
            int v = Key[e];
            if(d[v] > d[x] + w[e]){
               d[v] = d[x] + w[e];    //松弛成功，更新d[v]
               q.push(make_pair(d[v],v));//加入队列
            }
        }
    }
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        top = 0;
        memset(Head,-1,sizeof(Head));
        for(int i = 0;i != m;++i)
        {
            int x,y,cost;
            cin>>x>>y>>cost;
            Add(x,y,cost);
        }
        int s;
        cin>>s;
        Dijkstra(s,n);
        for(int i = 1;i <= n;++i)
           cout<<"i = "<<i<<" d = "<<d[i]<<endl;
        cout<<endl;
    }
    return 0;
}

解释一下上面的if(u.first != d[x])continue;这里也可以用一个标记数组来实现，但是要耗费一些内存，所以这里我就不用标记数组来判断该点是否实现过了。我解释一下为什么可以那样来判断呢？首先我们先想想，当有一个节点x已经更新过了压入队列.我们设当前再次遇到x节点的时候,我们此时记x为x'(x=x')则这次更新的d[x']一定比已经在队列里的小(d[x]>d[x'])，所以此时x'(x=x')会再次压入队列。而x'(d[x'])先于之前x(d[x])已经在队列中的点先出队列。所以，之前在队列里的那个x(d[x])就无需再出队列进行再次对其他结点松弛了。

表述的可能有点乱，那就直接实例分析吧：

1 3 1

1 2 3

3 2 1

2 4 1

上面分别代表两个顶点和权值。

首先，我们设起点为1,则我们先把2,3压入队列,（此时d[2] = 3,d[3] = 1），所以下一次更新的是3这个节点，这时对2节点进行松弛操作将更新2节点即d[2] = 2,这时在将其压入队列，此时队列中就会存在两个2节点了，而我们在用2节点对其他点进行松弛的时候，只要用最短的一个就好了(即，d[2]=2)。ok，解释完毕。不知道你懂了没有。