用C语言编程实现最短路径.doc

用C语言编程实现最短路径 摘 要: 最短路径问题研究的问题主要有：单源最短路径问题、与所有顶点对之间的最短路径问题。在我们的生产生活中遇到最短路径的问题实在太多了，比如乘汽车旅行的人总希望找出到目的地尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？我们首先应该建立它的数学模型，借助图、矩阵等数学工具，然后根据数学模型写出的算法及其源程序。 关键词：C语言，编程，最短路径 中图分类号：G343 Programs the realization most short-path wages hibiscus with the C language Xinjinrong (east Gansu institute computer and the information science institute 2007 level of 4 class of Gansu Qingyang 745000) the abstract: The most short-path question research question mainly has: Simple source most short-path question, and all apexes to between most short-path question.Met the most short-path in ours production life the question too to be really many, for instance rode the automobile travel the human always hoped discovered to destination as far as possible short traveling schedule.If has a map and leaves in the chart superscript every time to between the intersection distance, how discovers this shortest traveling schedule? We first should establish its mathematical model, with the aid of mathematical instruments and so on the chart, matrix, then the algorithm and the source program which writesaccording to the mathematical model. Key word: C language, programming, most short-path Chinese Library classification number: G343 1最短路径及其相关概念 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两节点之间的最短路径。算法具体的形式包括： （1）确定起点的最短路径问题——即已知起始结点，求最短路径问题。 （2）确定终点的最短路径问题——与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，再有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （3）确定起点终点的最短路径问题——即已知起点和终点，求两结点之间的最短路径。 最短路径问题研究的问题主要有：单源最短路径问题、与所有顶点对之间的最短路径问题。 1.1最短路径的基本概念 1.2与其相关的概念 为了更好理解什么是最短路径，首先我们就该清楚以下的问题。 （1）） （2）形成数学模型； （3）求解数学问题； （4）研究算法，并尽量使用计算机； （5）回到实际中去，解释结果。 最短路径的实现必须借助图、矩阵等数学工具。 3.2具体实现举例 已知交通，求使总费用最小的旅行路线。）……，n；E为有向边集，有边表示两站之间是相通的；W为边上的权集，边上标注的数字表示边的大小，边的大小表示费用；箭头指向的结点为终止结点，没有箭头的边表示这两站之间相互通车，费用相同。 3.2.2用邻接矩阵表示有向图G 邻接矩阵是表示顶点之间相邻关系的矩阵，设G=(V,E)是具有n个顶点的图，则G的领接矩阵是具有如下性质的n阶方阵： 3.2.3矩阵的运算及其意义 An表示两结点之间长度为n的通路，这里的长度是指两结点之间边的数目。所以我们要计算出An（n的取值为结点的个数）。 A2=× 在求出An后我们就可求出可达性矩阵， Rn=A+A2+A3+…+An 一个图G的可