5．9 网络分析

    网络分析在地理信息系统中有着广泛的应用领域。例如在城市规划设计中，通信线路的铺设，交通管理中交通路线的确定，以及旅游工作中新路线的开辟等。

    这里所说的网络，不是指计算机网络，而是由一组线状要素相互联结组成的。这种网络分析的理论基础是图论，所用数据结构为非线性图数据结构。

    网络分析的典型应用是求最短路径问题。最短路径分析是根据网络的拓扑性质，求图数据结构中，从一个顶点出发到其它各顶点之间的最短路径，或求每对顶点之间最短路径。

    最短路径实质上是求加权后的最短路径。例如：在交通运输中从A地到B地的最短路径，不一定是最佳路径，因为道路可能有上坡、下坡、路面质量，还需考虑由于车的流量引起的拥挤等因素。为此，可对两点之间给予权重值，以表示两点之间有效距离，可能化费的时间，或费用等。从而，若两点之间有很多道路可通情况下，可求出什么路线距离最短，什么路线化的时间最少，什么路线最节省费用等。考虑到道路的单向性，这里用有向图来表示之。图中每个顶点表示一地点、边表示各地点之间距离。路径的长度是指路径上各边的加权值之和。路径的起始点称为源点，路径的最后一顶点称为终点。

    这里讨论从某个源点到其余各点的最短路径问题。

    设有5个地点V1，V2，V3，V4和V5相互间通路如图5-35有向网络图所示。图中各边上所标的数字为该边具有的权重值。

    现以V1为源，求它到V5点的路径为：

    ＜V1，V5＞长度为100

    ＜V1，V4，V5＞长度为30+60=90

    ＜V1，V4，V3，V5＞长度为30+20+10=60

    ＜V1，V2，V3，V5＞长度为10+50+10=70

    显然路径＜V1，V4，V3，V5＞长度最短。尽管它含有3条边，但仍比含有一条边的＜V1，V5＞路径为短。表5-7表示了从V1出发到各点的最短路径。

    现在的问题是如何求得表5-5的最短路径。荷兰人迪杰斯特拉(Dijkstra)在1959提出了一种求最短路径的算法，被广泛采用，称之为迪杰斯特拉算法。这种算法实质上是一种按路径长度递增的次序求最短路径。他认为从源出发求到达其它顶点的最短路径时，当前正在生成的最短路径上除终点之外，其余顶点的最短路径均已生成。例如，生成V1到V5的最短路径＜V1，V4，V4，V5＞时，＜V1，V4，V3＞的路径已生成。这是因为＜V1，V4，V3＞的路径比＜V1，V4，V3，V5＞的最短路径长度短。

    根据这个思路，首先求出有向图的带权的邻接矩阵cost。

    其中cost[i，j]表示有向边＜Vi，Vj＞上的权重值。若＜Vi，Vj＞不存在，则取cost[i，j]=∞。若i=j则取cost[i，j]=0。按图5-35所示，首先，从V1源出发的各边中选取权重值最小的边，作为源点V1出发的最短路径。而下一个次短路径Vk可能是＜V1，Vk＞，或者是＜Vi，Vj＞和＜Vj，Vk＞权重值之和。这样每求出某个顶点的最短路径之后，就有可能对其它尚未最终确定最短路径的顶点的最短路径长度产生影响。若这里引入一个辅助向量dist，它的每个分量dist[i]表示当前找到从始点V到每个终点Vi的最短路径的长度，S为已求得的最短路径的终点的集合。则算法的描述可归纳成如下步骤：

    1)求从V出发到图上各顶点Vi(终点)，可能达到的最短路径长度的初值，dist[i]。

    2)选择Vj，使得

    Vj为当前的一条从V出发的最短路径的终点。

    3)修改V出发到集合V-S上的所有顶点Vk可能达到的最短路径长度。如果

dist[j]+cost[j，k]＜dist[k]

    则修改dist[k]为

dist[k]=dist[j]+cost[j，k]

    4)重复2)，3)步，直到求得V到图上的各个顶点的最短路径长度递增序列为止。

    图5-36为该算法求单源最短路径的示例图。

    根据邻接矩阵对有向图执行该算法，得到表5-6。

    从V1点到其余各顶点的最短路径以及运算过程中，dist向量的变化状况如下：从V1开始由图5-36(a)得，最短路径V1→V2，长度为10；

    从V1开始由图5-36(b)得，次短路径V1→V4，长度为30；

    从V1开始由图5-36(c)得，更次短路径V1→V4→V3，长度为50；

    从V1开始由图5-36(d)得，最次短路径V1→V4→V3→V5，长度为60；

    图5-36(e)为所得最短路径全貌图。

    上述最短路径分析是从某源点出发求到其他各点的最短路径。若要求每对顶点之间的最短路径，实际上是每次以一个顶点为源，重复执行上述算法。