文档介绍：
在空间网络分析中,路径问题占有重要位置。人们常想知道在地理空间网络的两指定结点间是否存在路径,如果有则特别希望找出其中的最短路径。
这种路径问题对于交通、消防、信息传输、救灾、抢险等有着重要的意义。
在运输网络中,有时要找出运输费用最小的路径;在通讯网络中,要找出雨点间进行信息传递具有最大可靠性的路径等等。
由于大量的最优化问题等价于找一个网络图的最短路径的问题,因而引起了人们对于最短路径分析的极大兴趣。
下面介绍的最短路径搜索算法是Dijkstra在l959年提出的,被公认为是最好的算法之一。
Dijkstra算法
Dijkstra算法是一种求单源最短路的算法,即从一个点开始到所有其他点的最短路。
Dijkstra算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合,而边的权重则由权重函数w: E → [0, ∞]定义。 因此,w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。
 已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低花费路径(. 最短路径)。 这个算法也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。
Dijkstra算法
其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离。当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性。不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破坏了已经更新的点距离不会改变的性质。
如果用本算法求一个图中全部的最短路,则要以每个点为源调用一次Dijkstra算法。
算法描述