最短路径问题在实际生活中的应用(2)
1.3 预备知识
最短路径问题是图论研究中的一个经典问题[6]。短路径首先要了解图论的有关知识，图论起源于18世纪，图论中所谓的图是指某类具体事物和这些事物之间的联系，人们经常用点表示这些具体的事物，用连接两点之间的线段表示这两个事物之间的特定的联系，点的空间位置和边的曲直长短都是无关紧要的，重要的是图中的点之间有哪几条边相连。
一个有序二元组 称为一个图,记作 ， 或者 称作顶点集， 是有限非空集，其中的元素称为顶点或者节点，简称点 或者 称为 的边集。它是连接 中的顶点，如果这两个节点是无序的称为无向边，否则称为有向边。如果在图 中，任意一对 中都赋有一个数 可以得到一个赋权图，记作 ，对于赋权图路的长度通常指路上所有的边的权之和。而赋权图上指定顶点之间的权最小的路就是最短路径问题。
最短路径顾名思义就是在所有的路径中找到一条距离最短的路径，通常所讲的不仅包括地理上的距离最短，还包括费用最少或者时间最短等问题[3]，因此最短路径也可以看作是最优路径问题。在实际生活中所找的最短路径问题可以转化成最优解的问题。它包含有很多算法，其算法的具体形式包括：第一、确定起点的最短路径问题就是已知起始结点，求最短路径的问题。第二、确定终点的最短路径问题(与确定起点的问题相反)，就是已知终结结点，求最短路径的问题。可分为有向图和无向图，在有向图中该问题等同于把所有路径方向反转的确定起点的问题，在无向图中该问题与确定起点的问题完全等同。第三、确定起点终点的最短路径问题 就是已知起点节点和终点节点，求两结点之间的最短路径。第四、全局最短路径问题即求图中所有的最短路径[8]。适合使用Floyd-Warshall算法。
最短路径有以下两个定义：
定义1：在图 中各边e都赋有一个实数 ，称为边e的权，则称这种图为赋权图，记为 。
定义2： 是赋权图并且 ， ,若 是 到 的路 的权,则称 为 的长,长度最小的 到 的路 称为最短路。
2. 最短路径问题的算法
图可以分为无权图和有权图，无权图中如果从一个顶点到另外一个顶点之间存在着一条路径，就称该路径上所经过的边数为该路径长度，它等于该路径上的顶点数减1。带权图的最短路径问题就是求两个顶点之间长度最短的路径，路径的长度是指路径上各个边的权值之和，路径边上的权值代表的意义决定了路径长度的具体含义。通常把一条路径上所经过的边的权值之和规定为该路径的路径长度，最短的那条路径称为最短路径，那些用于解决最短路径问题的算法就被称为“最短路径算法”，有时也称作为“路径算法”[11]。
最短路径的计算方法可以分为两种，一种是静态最短路径算法另外一种是动态最短路径算法，静态最短路径算法是在外界条件不变的情况下计算出来的，动态最短路径算法是在外界条件不断发生变化的情况下计算出来的。最常用的最短路径算法有：Dijkstra算法、 算法、Floyd算法等算法[3]。在动态算法中比较经典的是D*算法，本文主要讨论的应用主要是在公交交通网络等静态网络中，因此对于动态最短路径D*算法不做详细的介绍。
迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法，是目前国内外一致公认的较好算法，他们是求解网络图上各个节点之间最短路径的算法，在这两种算法中网络被抽象为一个有向或者无向图，并利用图的节点邻接矩阵（赋权）来记录点之间的关联信息[10]。在搜索最短路径时，以该矩阵为基础，通过不断的判断和更新目标的最小值，找出最短路径，也就是实际生活中的最优解。
下一篇：浅析云安全+文献综述+参考文献