数据结构实验报告-最短路径.doc

实验报告

实验名称最短路径

课程名称数据结构与算法实验
|
|
专业班级：信息安全

学号：

姓名：

实验六最短路径
一、实验目的
1.学习掌握图的存储结构
2.学会编写求最短路径的算法
二、实验内容
1、实验题目
编写代码实现Dijkstra生成最短路径的算法，其中要有完整的图的输入输出
2、简单介绍
图的存储：用邻接矩阵，这样会方便不少。
邻接矩阵是一个二维数组，数组中的元素是边的权（一些数值），数组下标号为结点的标号。
（1）例如二维数组中的一个元素M[5][6]的值为39，则表示结点5、6连接，且其上的权值为39。
（2）用邻接矩阵存储图，对图的读写就简单了。因为邻接矩阵就是一个二维数组，因此对图的读写就是对二维数组的操作。只要能弄清楚边的编号，就能把图读入了。
用一对结点表示边（也就是输入的时候输入一对结点的编号）
求最短路径的算法：
求最短路径就是求图中的每一个点到图中某一个给定点（这里认为是编号为0的点）的最短距离。
具体算法就是初始有一个旧图，一个新图。开始的时候旧图中有所有的结点，新图中初始为只有一个结点（源点，路径的源头）。整个算法就是不停的从旧图中往新图中添加点，直到所有的点都添加到新图中为止。
要实现这个算法，除了用二维数组保存图，还需要使用到两个辅助的数组
数组find[N]：此数组是用来表示标号对应的结点是否已经被添加到新图中（因为只有旧图中的点我们才需要添加到新图中，并且只有旧图中点到源点的距离，我们才需要进行更新）其中N为图中结点的个数。
数组distance[N]：此数组记录图中的点到源点的距离。这个数组里面存放的值是不断进行更新的。其中N为图中结点的个数。

3、程序简单模板
只是参考，不需要照着这个来写
//最短路径
#ifndefMYGRAPH_H_
#defineMYGRAPH_H_
classMyGraph
{
public:
voidreadDirectedGraph();
MyGraph(intsize);//构造函数中设置图的大小，分配空间
voidwriteGraph();
voidshortPath(intsource);//求最短路径

protected:
private:
int**m_graph;//用二维数组保存图
intm_size;//图的大小

};
#endif
/////////////////////////////////////////////////////////////////////
//构造函数中设置图的大小，分配空间
MyGraph::MyGraph(intsize)
{
inti,j;
m_size=size;
//给图分配空间
m_graph=newint*[m_size];
for(i=0;i<m_size;i++)
{
m_graph[i]=newint[m_size];
}
for(i=0;i<m_size;i++)
{
for(j=0;j<m_size;j++)
{
m_graph[i][j]=INT_MAX;
}
}
}

三、实验代码

#include<iostream>
#include<iomanip>
#include<stack>
#include<deque>
#include<fstream>
usingnamespacestd;
structprimnode
{
public:
charbegvex;
charendvex;
intlowcost;
};
structadknode
{
intdist;//最近距离
charway[50];//顶点数组
intnodenum;//经过的顶点数
};
classMgraph//邻接矩阵储存结构
{
public:
Mgraph(){}
~Mgraph(){}
voidCreatMGraph();
voidDFS(int);//用递归实现
voidDFS1(int);//非递归
voidBFS(int);
voidprint();
voidprim();
intmini();
intlow();//最短距离函数的辅助函数
intLocateVex(char);
voidkruskal();
voidDijkstra();
voidFloyd();
private:
intnumber;//顶点数目
intarcnum;//边的数目
charvexs[50];
intarcs[50][50];
intvisited[50];//便利时的辅助工具
primnodecloseedge[50];//prim
adknodedist[50];//最短路径
intD[20][20];//f