贪心法求解单源最短路径问题
虽说之前贴了模版 = = 但还是按照老师的格式写一下……
每次找到距离源点最接近且未被访问的点，对该点能到达的所有结点遍历比较经过该点中转后的距离是否小于之前计算的最短距离，是则更新该结点距离（若之前没访问过还要置其访问标记为真）。最多查找n-1次各遍历过一遍后即可得出最终解。
【模板】Dijkstra - 单源最短路径
当年整理得 - -
-
#define N 1002
-
#define MAX 99999
-
int edges[N][N],d[N],n;
-
-
void dijkstra(int v)
-
{
-
int i,j;
-
bool s[N]={false};
-
for(i=1;i<=n;i++)
-
d[i]=edges[v][i];
-
d[v]=0;s[v]=true;
-
for(i=1;i<n;i++)
-
{
-
int temp=MAX;
-
int u=v;
-
for(j=1;j<=n;j++)
-
if((!s[j])&&(d[j]<temp))
-
{
-
u=j;
-
temp=d[j];
-
}
-
s[u]=true;
-
for(j=1;j<=n;j++)
-
if((!s[j])&&(edges[u][j]<MAX)&&(d[u]+edges[u][j])<d[j])
-
d[j]=d[u]+edges[u][j];
-
}
-
-
}
调用时，初始结点s，目标结点e，则
dijkstra(s);
cout<<d[e]<<endl;
即可。
注意结点是从1存储到N。
不能连通时值为MAX。
Til the Cows Come Home
pku 2387：http://acm.pku.edu.cn/JudgeOnline/problem?id=2387
从n地走到1地，求最小距离。典型的单源最短路径，直接套模板……
