动态规划求多段图单源最短路径
从终点n-1开始，直到顶点0，对每个点：
遍历其所能达到的各个结点，判断通过该结点访问终点的路径是否小于当前能找到的最短距离，是则更新，否则不变。
最后，顶点0找到的最短距离必然是该点到达终点n-1的最短距离。
* 局限性：本程序只能求从顶点0到顶点n-1的最短路，且只能从编号较小的点访问编号较大的点。
贪心法求解单源最短路径问题
虽说之前贴了模版 = = 但还是按照老师的格式写一下……
每次找到距离源点最接近且未被访问的点，对该点能到达的所有结点遍历比较经过该点中转后的距离是否小于之前计算的最短距离，是则更新该结点距离（若之前没访问过还要置其访问标记为真）。最多查找n-1次各遍历过一遍后即可得出最终解。
【模板】SPFA - 单源最短路径
看了wekooo给的某论文，从里面pascal翻过来 = =
-
void SPFA(int s){
-
for(int i=1;i<=n;i++){
-
d[i] = MAX;
-
}
-
int queue[N*N] = {0};
-
bool visit[N] = {false};
-
int front = 0, rear = 1;
-
//int path[N];
-
queue[front] = s; visit[s] = true; d[s] = 0;
-
while(front<rear){
-
int u = queue[front];
-
visit[u] = false;
-
for(int i=1; i<=n; i++){
-
if (d[i]>d[u]+ edges[u][i]){
-
d[i]= d[u]+edges[u][i];
-
//path[i] = u;
-
if( !visit[i] ){
-
visit[i] = true;
-
queue[rear++] = i;
-
}
-
}
-
}
-
front++;
-
}
-
}
调用时，初始结点s，目标结点e，则
SPFA(s);
cout<<d[e]<<endl;
即可。
注意结点是从1存储到N。
不能连通时值为MAX。
【模板】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地，求最小距离。典型的单源最短路径，直接套模板……
