Dijkstra算法

特点：是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

举例说明：

图例来自《算法导论》

注意：要求图中不存在负权边。

朴素：

void init()
{
	memset(vis,0,sizeof(vis));	memset(d,0,sizeof(d));	memset(p,0,sizeof(p));
	vis[sta]=1;
	for(int i=1;i<=n;++i)		d[i]=a[sta][i];
	for(int i=1;i<=n;++i)		p[i]=sta;
	d[sta]=0;	p[sta]=0;
}
void Dijkstra()
{
	int k;	init();
	for(int i=1;i<=n-2;++i)
	{
		m=max1;
		for(int j=1;j<=n;++j)
		{
			if(d[j]<m && !vis[j])
			{m=d[j];	k=j;}
		}
		if(m==max1)		break;
		vis[k]=1;
		for(int j=1;j<=n;++j)
			if(d[k]+a[k][j]<d[j])
			{
				d[j]=d[k]+a[k][j];
				p[j]=k;
			}
	}
	printf("%d",d[end]);
	return ;
}

堆优化：

#include<bits/stdc++.h>
#define MAXN 100010
#define MAXM 500010
#define INF 0x3f3f3f3f
struct EDGE{int to,dis,next;}	e[MAXM];
struct node
{
    int dis,pos;
    bool operator <( const node &x ) const	{return x.dis < dis;}
    //重定向
};
std::priority_queue< node > q;
int n,m,s;
int adj[MAXN],dis[MAXN],cnt;
bool vis[MAXN];
void addedge(int u,int v,int d)	//链式前向星
{
    ++cnt;
    e[cnt].dis=d;	e[cnt].to=v;
    e[cnt].next=adj[u];
    adj[u]=cnt;
}
void Dijkstra()
{
    dis[s]=0;	q.push(( node ){0,s});	//先将源点入队列
    while(!q.empty())
    {
        node temp=q.top();	q.pop();
        int x=temp.pos;
        	if(vis[x])	continue;		//对未访问节点进行扫描
        vis[x]=1;
        for(int i=adj[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( (node){dis[y], y} );	//邻接节点入队列
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;++i) dis[i]=INF;		//初始化
    for(int i=0;i<m;++i)
    {
        int u,v,d;	scanf("%d%d%d",&u,&v,&d);
        addedge(u,v,d);
    }
    Dijkstra();
    for(int i=1;i<=n;++i)	printf("%d ",dis[i]);
    return 0;
}

做题感悟：

• 有的题目是在问题中套着最短路的模型，要分析出题目中所求的“路径”，然后使用Dijkstra算法。
• 在“三角不等式”的部分注意，有些题目是运用Dijkstra的思想，但最后所求答案的计算公式并是不“三角不等式”。