最短路径
交通网络可以画成带权的图，图中顶点表示城市，边代表城市
间的公路，边上的权表示公路的长度。对于这样的交通网络常常提
出这样的问题：两地之间是否有公路可通？在有几条路可通的情况
下，哪一条路最短？以上提出的问题就是在带权图中求最短路径问
题，此时路径的长度不是路径上边的数目，而是路径上的边所带权
值的总和。
设 A 城到 B 城有一条公路， A 城的海拔高于 B 城，若考
虑到上坡和下坡的车速不同，则边 <A,B> 和边 <B,A> 上表示行
驶时间的权值也不同，即<A,B> 和 <B,A> 应该是两条不同的边，
考虑到交通网络的这种有向性，本节只讨论有向网络的最短路径问
题，并假定所有的权为非负实数。习惯上称路径开始顶点为源点，
路径的最后一个顶点为终点。
1、最短路径定义
所谓最短路径问题是指：如果从图中某一顶点（源点）到达另
一顶点（终点）的路径可能不止一条，如何找到一条路径似的沿此
路径上各边的权值总和（称为路径长度）达到最小。
2、单源最短路径
单源最短路径问题：已知有向带权图(简称有向网)G=(V，E)，找
出从某个源点 s∈V 到 V 中其余各顶点的最短路径。
迪杰斯特拉(Dijkstra)算法求单源最短路径
由 Dijkstra 提出的一种按路径长度递增序产生各顶点最短路径
的算法。
（1）按路径长度递增序产生各顶点最短路径
若按长度递增的次序生成从源点 s 到其它顶点的最短路径，则
当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已
生成（将源点的最短路径看作是已生成的源点到其自身的长度为 0
的路径）。
【例】在有向网 G8 中，假定以顶点 0 为源点，则它则其余各顶点
的最短路径按路径递增序排列如右表所示
（2）具体做法
一开始第一组只包括顶点 v 1 ，第二组包括其他所有顶点， v
1 对应的距离值为 0 ，第二组的顶点对应的距离值是这样确定的：
若图中有边 <v 1 , v j >, 则 v j 的距离为此边所带的权值，否则 v j
的距离值为一个很大的数 ( 大于所有顶点间的路径长度 ) ，然后
每次从第二组的顶点中选一个其距离值为最小的 v m 加入到第一
组中。每往第一组加入一个顶点 v m ，就要对第二组的各个顶点
的距离值进行一次修正。若加进 v m 做中间顶点，使从 v 1 到 v
j 的最短路径比不加 v m 的路径为短，则要修改 v j 的距离值。
修改后再选距离最小的顶点加入到第一组中。如此进行下去，直到
图中所有顶点都包括在第一组中，或再也没有可加入到第一组中的
顶点存在为止。
假设有向图 G 的 n 个顶点为 1 到 n, 并用邻接矩阵 cost
表示 , 若 < v i , v j > 是图 G 中的边，则 cost[i][j] 的值等于边所
带的权 ; 若 <v i , v j > 不是图 G 中的边，则 cost[i][j] 等于一个
很大的数；若 i=j, 则 cost[i][j]=0 。另外 , 设置三个数组 S[n] 、
dist[n] 、 pre[n] 。 S 用以标记那些已经找到最短路径的顶点，若
S[i-1]=1, 则表示已经找到源点到顶点 i 的最短路径 , 若 S[i-1]=0,
则表示从源点到顶点 i 的最短路径尚未求得。 dist[i-1] 用来记录
源点到顶点 i 的最短路径。 pre[i-1] 表示从源点到顶点 i 的最短
路径上该点的前趋顶点，若从源点到该顶点无路径，则用 0 作为
其前一个顶点序号。
（3）迪杰斯特拉算法
voi DijGraph::ShorttestPath_Dijkstra(int v)
{ //G 是一个具有 n 个顶点的带权有向图，求从源点 v 到其余各
顶点的最短路径长度
for(int i=0;i<n;i++) //dist，path，S 的初始化
{ dist[i]=Edge[v][i];S[i]=0;
if(i!=v&&dist[i]<MAXNUM)path[i]=v;
else path[i]=-1; //顶点 i 无前顶点
}
S[v]=1; //顶点 v 加入已求出的最短路径的顶点集合
dist[v]=0;
for(i=0;i<n;i++ //求其余 n-1 个顶点的最短路径
{float min=MAXNUM;
int u=v;
for(int j=0;j<n;j++) //选择当前不在集合 S 中具有最短路径的
顶点 u
if(!S[j]&&dist[j]<min){u=j;min=dist[j];}
S[u]=1; //顶点 u 加入到已求出最短路径的顶点集合
for(int w=0;w<n;w++) //修改期于顶点的当前最短路径
if(!S[w]&&Edge[u][w]<MAXNUM&&dist[u]+Edge[u][w]<dist[w])
{ dist[w]=dist[u]+Edge[u][w];
path[w]=u;}
}
}
其他最短路径问题
最短路径问题的提法很多，其它的最短路径问题均可用单源
最短路径算法予以解决：
① 单 目 标 最 短 路 径 问 题 (Single-Destination Shortest-Paths
Problem)：找出图中每一顶点 v 到某指定顶点 u 的最短路径。只需
将图中每条边反向，就可将这一问题变为单源最短路径问题，单目
标 u 变为单源点 u。
② 单 顶 点 对 间 最 短 路 径 问 题 (Single-Pair Shortest-Path
Problem)：对于某对顶点 u 和 v，找出从 u 到 v 的一条最短路径。
显然，若解决了以 u 为源点的单源最短路径问题，则上述问题亦迎
刃而解。而且从数量级来说，两问题的时间复杂度相同。
③ 所 有 顶 点 对 间 最 短 路 径 问 题 (All-Pairs Shortest-Paths
Problem)：对图中每对顶点 u 和 v，找出 u 到 v 的最短路径问题。
这一问题可用每个顶点作为源点调用一次单源最短路径问题算法
予以解决。
单链表的插入
（1）思想方法
插入操作大致分为如下三种：
①在已知 P 指针所指向的结点后插入一个元素 x。
②在 p 指针所指向的结点前插入一个元素 x。
③在线性表中值为 y 的元素插入一个值为 x 的数据元素。
大致算法思想：插入运算是将值为 x 的新结点插入到表的第
资源评论
