文档介绍：-
. z.
目录
目录1
摘要2
Abstract3
第一章绪论4
第二章最短路径问题e again encountered this kind of problem, can save a lot of manpower and material resources to greatly improve the e
-
. z.
fficiency of the work.
Keywords:dijkstra algorithm, Floyd algorithm, bellman-ford algorithm, SPFA algorithm .
绪论
近年来，随着社会经济的飞速开展和人们生活水平的不断提高，汽车越来越成为人们不可或缺的交通工具。汽车数量的急剧增加使得城市道路交通日益复杂，而交通设施的建立远远落后于汽车数量的增加，因此交通堵塞现象十分严重，交通事故也愈发频繁。将最短路径算法应用于车辆导航系统，公交查询系统，将会提高行车效率，有效防止交通堵塞以及交通事故的发生，无疑是解决交通问题的利器，也是智能交通的具体表现。
随着城市经济的开展、规模的扩大以及人口的增长，城市交通问题日益突出。降低出行时间将使所有的国民产生效益，快速的交通、更好的信息及更好的市场可以提高城市的形象，能够带动经济增长。城市公共交通运输以其覆盖面广、经济、快捷的特点，成为绝大多数出行者的首选方式，也是各地城市政府大力开展的一种交通方式。本地市民特别是外来旅游、出差、就医等就急需了解本地道路情况，从而选择一个最优路线。
-
. z.
我国城市道路的开展处于一个落后的水平,广阔驾驶者可以获得信息的方式很少,道路长期堵塞。道路实时信息的完整性和准确性得不到保证,而且还没有专门的机构负责信息的发布和管理。
本文通过对几种最短路径算法的研究，比拟找到适合城市道路路线选择的算法，用于改善城市的交通。
近年来，离散数学经过飞速开展，已成为我们研究中不可缺少的一局部，而它的一个分支图形学与计算机严密地结合在一起，更成为广阔学者的研究对象，逐渐的独立成章，越加的成熟起来。图的分类很细,也很广泛,大方向可分为有向图和无向图,而计算机中常用的树也是一种特殊的图。图的表示方法:邻接矩阵,完全关联矩阵,。
最短路径问题是图论中的一个典问题，，如：GIS网络分析、城市规划、，寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子.
由于最短路径问题的广泛应用，很多学者都对此进展了深入的研究，，对最短路径研究的热度依然不减，，.
-
. z.
第二章 最短路径问题的根底知识
图的根本概念
V1
V2
V3
V4
V5
图1
图：图是一种较线形表和树更为复杂的数据构造。在图形构造中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。：在保持图的点边关系不变的情况下，图形的位置、大小、。
弧： 两个顶点之间关系的集合VR,<v,w>VR,表示从v到w的一条弧。称v为弧尾，w为弧头。假设<v,w> 为一条有向弧，则称该图为有向图；
假设〔v,w〕为无向弧，此时的图称为无向图。
完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。在有向图中，如果任意两项顶点之间都存在方向互为相反的两条弧，则称该图为由向完全图。
稀疏图、稠密图：由很少边的图称为稀疏图。反之，成为稠密图。稀疏和稠密本身是模糊的概念，稀疏和稠密常常是相对而言的。
邻接点：对于无向图G=〔V，{E}〕，如果边〔v,w〕E,则称顶点v和w互为邻接点。
度：以顶点v为头的弧的数目称为v的入度，以顶点v为尾的弧的数目称为v的出度，出度和入度统称为度。
路径：无向图G=〔V，{E}〕中从顶点v到顶点