最短路径dijkstra

dijkstra本质上的思想是贪心,它只适用于不含负权边的图.
我们把点分成两类,一类是已经确定最短路径的点,称为"白点",另一类是未确定最短路径的点,称为"蓝点"dijkstra的流程如下

1. 初始化dis[start]=0,其余节点的dis值为无穷大.
2. 找一个dis值最小的蓝点x,把节点x变成白点.
3. 遍历x的所有出边(x,y,z),若dis[y]>dis[x]+z,则令dis[y]=dis[x]+z
4. 重复2,3两步,直到所有点都成为白点

priority_queue<pair<int,int> ,greater<int> > q;
void dijkstra()
{
    dis[s] = 0;
    q.push( ( make_pair(0,s));
    while( !q.empty() )
    {
        int x = q.top().first, d = q.top().second;
        q.pop();
        if( vis[x] )
            continue;
        vis[x] = 1;
        for( int i = head[x]; i; i = e[i].next )
        {
            int y = e[i].to;
            if( dis[y] > dis[x] + e[i].dis )
            {
                dis[y] = dis[x] + e[i].dis;
                if( !vis[y] )
                {
                    q.push( make_pair(dis[y], y) );
                }
            }
        }
    }
}