【题解】求一个无向图的最短路径（dijkstra）

题目描述

一个含n个结点的无向图，以矩阵存储方式给出，请求出指定的两个点之间的最短距离。

输入格式：

第一行，一个整数n（0 < n < 1000 ），表示无向图中结点的个数。
接下来是一个n*n的矩阵，表示无向图中各结点之间的联结情况，矩阵中的数值为小于等于1000的下整数，其中 0 表示两点之间无直接连接。
最后一行，两个整数i,j。表示求解i点到j点的最短距离。

输出格式：

一个数值，表示指定的两点之间最短距离。

输入样例#1：

2
0 2
2 0
1 2

输出样例#1：

2

【解题分析】

这是比较直白的一个单源点最短路问题，使用dijkstra算法，给每个节点设置标号，dis[i]表示从源点到第i个点的最短路的值，每次从还没标记的点里面找一个最小的dis值，将它标记掉（即确认该点的dis为它最短路），然后将这个点的所有有关联的点的dis进行更新，直到全部点处理完成。过程有点像贪心，每次取最小dis的值，但是需要不断的利用最新确定的点的dis值去更新其他点的dis值，对于所有边都是大于0的情况，这是必然可行的，这个更新的过程本质上是个DP的过程。

如果边权有负数呢？这个正确性就无法保证了，所以dijkstra算法只对正权边图有效。

进一步的，改算法的过程具有贪心性，每次取最小的dis，我们可以使用优先队列（二叉堆）对它 进行优化，提高它的运行效率。

【参考代码】

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PP;
const int nn=10005;
struct aty{
	int next,to,w;
}edge[nn];
int n,d[nn],head[nn],cnt=1,x,s,t;
void add(int u,int v,int w){
	edge[cnt].next=head[u];
	edge[cnt].to=v;
	edge[cnt].w=w;
	head[u]=cnt++;
}
void dijkstra(int s){
	priority_queue<PP,vector<PP>,greater<PP> > p;
	memset(d,0x3f,sizeof(d));
	d[s]=0;
	p.push(PP(0,s));
	while(!p.empty()){
		PP q=p.top();
		p.pop();
		int u=q.second;
		if(d[u]<q.first) continue;
		if(u==t) break;
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].to;
			if(d[v]>d[u]+edge[i].w)
				d[v]=d[u]+edge[i].w,
				p.push(PP(d[v],v));
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			cin>>x;
			if(x)add(i,j,x);
		}
	cin>>s>>t;
	dijkstra(s);
	cout<<d[t];
	return 0;		
}