数据结构课程设计大作业.pdf

数据结构课程设计大作业

130821班

题目最短路径问题

专业计算机科学与技术

学生姓名

学号******XX

指导教师唐国民

完成日期2014.11.25

湖州师院信息工程学院

目录

目录.1

最短路径问题.2

【内容摘要】.2

【关键字】.2

【Abstract】.2

【Keywords】.2

实验内容概述.1

实验目的概述.1

解题思路的描述.1

源程序清单.2

程序调试及测试结果.2

结论.7

参考文献.7

最短路径问题

【内容摘要】

【关键字】最短路径图论Floyd算法

【Abstract】

【Keywords】Shortestpath，Graphtheory，Floydalgorithm

计算机科学与技术专业数据结构大作业

实验内容概述

这是一幅美国硅谷的简单地图。对于此图，请写出一个完整的程序，对于输入的起点和

终点，输出它们之间的最短路径。

实验目的概述

在实际生活中诸如在运输路线、出外旅游路线、厂址选择等诸多方面都会有最短距离的

应用。

本实验中的问题是求任意两点间最短距离的问题，而实验的目的是运用邻接矩阵解决图

存储并解决在此结构情况下对矩阵中元素的扫描计算。其关键是怎样储存和计算。储存用的

是邻接矩阵，而计算用的是弗洛伊德算法。通过该实验更好地体会并进一步认识邻接矩阵，

知道弗洛伊德算法在解决任意两点之间最短距离问题方面上的优势。

解题思路的描述

本题是求美国硅谷中任意两点之间的最短距离，由于题意是求任意两点之间的最短路径

首先考虑到弗洛伊德算法，并且需要使用邻接矩阵来解决存储问题。

1