①唐巧玲　②郑晓敏

一、绪论

最短路径问题因为其问题的普遍性，以及应用的实际性，不仅是数据结构的热点问题，也是数学信息学科、计算机学科、地理信息学科等学科的一个研究热点。由于科学技术的不断进步，使得应用数学中的图论与计算机算法与结构结合，出现了不一样的较短路径算法。最短路径即点到点之间的路径是最短的，因此可以看作计算机中的图片问题，即如何从图片上找到两个顶点的路径所经过的最短路径，而最短路径算法也就提供了如何寻找某两点之间最短距离的思路。

二、最短路径算法介绍

最短路径是图论与复杂网络分析中的一个经典问题。最短路径算法则是将所需要求的问题，转化为图论问题，并通过相关的操作，最终得到问题所求的最短路径的过程。本文采用一个由n个节点和m条边组成的图G（V，E）作为路径图，V集合存放G中所有的顶点，E集合存放G中所有的边，将顶点之间存在的边的权值设为w。

（一）最短路径的基本概念

最短路径问题是求由源点到达图中其他任一顶点的最短路径，即在由节点构成的路径图中，找出一条经过路径的权值总和最短的路径。在图论研究中，假设将设置为源点，终点设为V_j，则寻找最短路径的形式有以下几种：

1、源点确定，求最短路径。

2、终点确定，求最短路径则需要进行讨论分析;若在无向图中，终点确定可以转化为顶点确定的问题来进行解决;若在有向图中，就需要将路径方向反转，通过找起点来确定此时终点确定下来的最短路径。……