最短路径问题设计

目 录

第1章 绪论 ................................................................................................................................................ 1

1.1 问题描述 ....................................................................................................................................... 1 1.2 问题分析 ....................................................................................................................................... 1 1.3 相关标识（名词定义）................................................................................................................ 1 1.4 本文主要研究内容........................................................................................................................ 2 第2章 算法设计与实现 ............................................................................................................................ 3

2.1 穷举法 ........................................................................................................................................... 3

2.1.1穷举法描述.......................................................................................................................... 3 2.1.2穷举法设计.......................................................................................................................... 3 2.1.3 穷举法分析......................................................................................................................... 6 2.2 回溯法 ........................................................................................................................................... 6

2.2.1 回溯法描述......................................................................................................................... 6 2.2.2 回溯法设计......................................................................................................................... 6 2.2.3 回溯法分析......................................................................................................................... 9 2.3 贪心法 ......................................................................................................................................... 10

2.3.1 贪心法描述....................................................................................................................... 10 2.3.2 贪心法设计....................................................................................................................... 10 2.3.3 贪心法分析....................................................................................................................... 12 2.4 动态规划法 ................................................................................................................................. 12

2.4.1 动态规划法描述 ............................................................................................................... 12 2.4.2 动态规划法设计 ............................................................................................................... 12 2.4.3 动态规划法分析 ............................................................................................................... 14

第3章 实验结果分析与算法对比 ........................................................................................................... 15

3.1 输入数据 ..................................................................................................................................... 15 3.2 实验结果与分析 ......................................................................................................................... 15 3.3 算法分析与对比 ......................................................................................................................... 17 第4章 总结与展望 .................................................................................................................................. 18 参考文献 .................................................................................................................................................... 19

1

第1章 绪论

1.1 问题描述

最短路径问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短，还可以引申到其它的度量，如时间、费用、线路容量等。

最短路径算法的选择与实现是通道路线设计的基础，最短路径算法是计算机科学与地理信息科学等领域的研究热点，很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。

本文主要解决的问题是：给定带权有向图G＝(V, E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。即给定一个有向图，再给出任意2个不相邻的顶点，求2个顶点之间的最短距离。

1.2 问题分析

给定一个带权有向图G＝(V, E)中的各个顶点之间的权值，对任意输入2个顶点

，求出从vi到vj的最短路径。 vi,vj∈V（i≠j）

输入：节点数目N，邻接矩阵VR[N][N]

约束条件：vi?vk?vm…vj 其中，vi,vk,vm,vj?V(i?k?m?j)

输出（目标函数）：min{ Dist(vi,vj) }

1.3 相关标识（名词定义）

（1）时间复杂度

算法的时间复杂性是指执行算法所需要的时间。一般来说，计算机算法是问题规模

1

n 的函数f (n)，算法的时间复杂性也因此记做T (n) ? O( f (n))。因此，问题的规模n越大，算法执行时间的增长率与f (n)的增长率正相关，称作渐进时间复杂性。 （2）空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法空间复杂度的计算公式记作：S(n)= O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。 （3）图的基本概念

图：由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=（V,E）。

有向图：在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图。 权：在图的边或弧中给出相关的数，称为权。 权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。

邻接矩阵：表示一个图的常用存储表示。它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

1.4 本文主要研究内容

本文共分为4章，具体组织结构如下：

第1章 绪论。本章主要对最短距离问题进行描述和问题进行分析，同时针对一些名词进行定义和解释。

第2章 算法的设计与实现。本章主要针对最短距离问题是用穷举法、回溯法、贪心法、动态规划法实现，并对算法进行描述、设计和分析。

第3章 实验结果分析与算法对比。本章主要对输入数据阐述，并对实验结果进行分析和算法分析与对比。

第4章 总结与展望。总结了本文的主要工作、重要贡献以及存在的不足，提出了进一步的工作内容，并对以后的研究工作进行了展望。

2