【数据结构算法】实验8 图的最短路径问题(附源代码)

数据结构实验课程名称数据结构实验题目名称图的最短路径实现学生学院应用数学学院专业班级信息计算1班学号3114008104学生姓名陈辉腾指导教师刘志煌2016年6月13日图的最短路径实现14信计1班—陈辉腾—3114008104实验要求：广东省主要大城市之间的交通图如下所示，每条边上的权值代表从城市A到城市B的路途长度，使用数据结构图的相关理论编程给出广州到各个城市的最短路径，并且输出经过的路径。

实验目的：进一步了解数据结构中对图的各种操作，以及求最短路径的算法。

实验内容：编程求解上述题目（实验要求）思路：首先把图用带权邻接矩阵g表示出来（每个城市看做一个顶点，广州是v0），然后用c语言实现书上的迪杰斯特拉算法，求有向网g的v0顶点到其余顶点v 的最短路径保存到D[v]，以及途经的一个最近新的路径保存Path[v]。

最后输出D[v]以及Path[v]。

构造领接矩阵代码如下（详细思路写在代码注释里面）：其中：（v0是广州；v1是佛山；v2是肇庆；v3是珠海；v4是深圳；v5是南宁；v6是香港）数据类型定义：构造上述领接矩阵函数代码：运行结果如下：求最短距离和路径函数如下：其中，PassPath(Path,i,v0)函数实现如下：SetName(i)函数（根据矩阵的行列数i，获得对应的城市名）实现如下：运行求解结果为：总结：一开始觉得图的好难，不过，确实很难啊，图比树复杂多了。

其实还有一部分原因是自己对图比较陌生的缘故吧。

对于这个求最短路径的算法的难点，个人觉得是在输出路径那里，巧妙的用到了递归。

还有我觉得，怎么把巧妙的吧途经最短路径保存下来？处理这个问题我就觉得是一个难点，把这个问题处理的好，输出时就比较不用那么麻烦。

书本是用一个二维数组p[][]和一个一维数组p[]来处理，两个数组名还一样，个人不太懂—>最后面一行没看懂，就是：p[w]=p[v];p[w][w]=TRUE;//p[w]=p[v]+[w],书本也没有对其路径的输出做处理，我也没有深究下去，而是参考别的资料采用另一种方法来处理（不过都是差不多的吧）。

python数据结构与算法——图的最短路径（Floyd-Warshall算法）使⽤Floyd-Warshall算法求图两点之间的最短路径不允许有负权边，时间复杂度⾼，思路简单1# 城市地图（字典的字典）2# 字典的第1个键为起点城市，第2个键为⽬标城市其键值为两个城市间的直接距离3# 将不相连点设为INF,⽅便更新两点之间的最⼩值4 INF = 999995 G = {1:{1:0, 2:2, 3:6, 4:4},6 2:{1:INF, 2:0, 3:3, 4:INF},7 3:{1:7, 2:INF, 3:0, 4:1},8 4:{1:5, 2:INF, 3:12, 4:0}9 }1011# 算法思想：12# 每个顶点都有可能使得两个顶点之间的距离变短13# 当两点之间不允许有第三个点时，这些城市之间的最短路径就是初始路径1415# Floyd-Warshall算法核⼼语句16# 分别在只允许经过某个点k的情况下，更新点和点之间的最短路径17for k in G.keys(): # 不断试图往两点i,j之间添加新的点k，更新最短距离18for i in G.keys():19for j in G[i].keys():20if G[i][j] > G[i][k] + G[k][j]:21 G[i][j] = G[i][k] + G[k][j]222324for i in G.keys():25print G[i].values()结果：[0, 2, 5, 4][9, 0, 3, 4][6, 8, 0, 1][5, 7, 10, 0]。

动态规划之最短路径问题源代码#include "stdio.h"#include "conio.h"#define n 16 /*图的顶点数*/#define k 7 /*图的段数*/#define l 30#define MAX 100typedef int NodeNumber;/*节点编号*/typedef int CostType;/*成本值类型*/CostType cost[n][n];NodeNumber path[k];NodeNumber cur=-1;void creategraph(CostType *cost[n][n]) /*创建图的成本矩阵*/ {int i,j,x,y,value;for(i=0;i<n;i++)for(j=0;j<n;j++) cost[i][j]=0;printf("\nEnter the cost of graph:\n");for(i=0;i<l;i++){scanf("%d,%d,%d",&x,&y,&value);cost[x][y]=value;}}void outgraph(CostType *cost[n][n]) /*输出图的成本矩阵*/ {int i,j;printf("Print the cost of graph:\n");for(i=0;i<n;i++){for(j=0;j<n;j++) printf("%2d",cost[i][j]);printf("\n");}}/*使用向前递推算法求多段图的最短路径*/void FPath(CostType *cost[n][n],NodeNumber *path[k]) {int i,j,leng,temp,v[n],d[n];for(i=0;i<n;i++) v[i]=0;for(i=n-2;i>=0;i--){ leng=MAX;for(j=i+1;j<=n-1;j++)if(cost[i][j]>0 && (cost[i][j]+v[j])<leng){leng=cost[i][j]+v[j];temp=j;}v[i]=leng;d[i]=temp;}path[0]=0;path[k-1]=n-1;for(i=1;i<=k-2;i++) path[i]=d[path[i-1]]; }/*输出最短路径序列*/void outpath(NodeNumber *path[k]){int i;printf("\nPrint the shortest treet:\n");for(i=0;i<k;i++) printf("%3d",path[i]); }main(){NodeNumber m,t;creategraph(&cost);outgraph(&cost);FPath(&cost,&path);outpath(&path);}。

目录交通咨询系统设计（最短路径问题）一、概述在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。

在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。

这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。

二、系统分析设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。

对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。

针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。

并未本系统设置一人性化的系统提示菜单，方便使用者的使用。

三、概要设计可以将该系统大致分为三个部分：① 建立交通网络图的存储结构；② 解决单源最短路径问题；③ 实现两个城市顶点之间的最短路径问题。

四、详细设计建立图的存储结构定义交通图的存储结构。

邻接矩阵是表示图形中顶点之间相邻关系的矩阵。

设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。

注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储顶点V的信息）。

i邻接矩阵的存储结构：附录#include<>#include<>#defineMVNum100#defineMaxint32767enumboolean{FALSE,TRUE}; typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum];}MGraph;intD1[MVNum],p1[MVNum];intD[MVNum][MVNum],p[MVNum][MVNum]; voidCreateMGraph(MGraph*G,intn,inte){inti,j,k,w;for(i=1;i<=n;i++)G->vexs[i]=(char)i;for(i=1;i<=n;i++)for(j=1;j<=n;j++)G->arcs[i][j]=Maxint;printf("输入%d条边的及w:\n",e);for(k=1;k<=e;k++){scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;}printf("有向图的存储结构建立完毕！\n"); }voidDijkstra(MGraph*G,intv1,intn){intD2[MVNum],p2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v<=n;v++){S[v]=FALSE;D2[v]=G->arcs[v1][v];if(D2[v]<Maxint)p2[v]=v1;elsep2[v]=0;}D2[v1]=0;S[v1]=TRUE;for(i=2;i<n;i++){min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}S[v]=TRUE;for(w=1;w<=n;w++)if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){D2[w]=D2[v]+G->arcs[v][w];p2[w]=v;}}printf("路径长度路径\n");for(i=1;i<=n;i++){printf("%5d",D2[i]);printf("%5d",i);v=p2[i];while(v!=0){printf("<-%d",v);v=p2[v];}printf("\n");}}voidFloyd(MGraph*G,intn){inti,j,k,v,w;for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(G->arcs[i][j]!=Maxint)p[i][j]=j;elsep[i][j]=0;D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++){for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j];p[i][j]=p[i][k];}}}}voidmain(){MGraph*G;intm,n,e,v,w,k;intxz=1;G=(MGraph*)malloc(sizeof(MGraph));printf("输入图中顶点个数和边数n,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);while(xz!=0){printf("************求城市之间最短路径************\n");printf("=========================================\n");printf("1.求一个城市到所有城市的最短路径\n");printf("2.求任意的两个城市之间的最短路径\n");printf("=========================================\n");printf("请选择:1或2，选择0退出:\n");scanf("%d",&xz);if(xz==2){Floyd(G,n);printf("输入源点（或起点）和终点:v,w:");scanf("%d,%d",&v,&w);k=p[v][w];if(k==0)printf("顶点%d到%d无路径!\n",v,w);else{printf("从顶点%d到%d最短路径路径是:%d",v,w,v);while(k!=w){printf("--%d",k);k=p[k][w];}printf("--%d",w);printf("径路长度:%d\n",D[v][w]);}}elseif(xz==1)printf("求单源路径，输入源点v:");scanf("%d",&v);Dijkstra(G,v,n);}printf("结束求最短路径，再见!\n"); }。

引言在图论中经常会遇到这样的问题，在一个有向图里求出任意两个节点之间的最短距离。

当节点之间的权值是正值的时候，我们可以采用Dijkstra算法，用贪心策略加于解决。

但当节点之间的权值有负数的时候，Dijkstra就行不通了，这里介绍另外一种算法—Floyd最短路径算法。

对于任意图，选择存储结构存储图并实现FLOYD算法求解最短路经。

将问题分解，分解为两方面。

一是对于任意图的存储问题，第二个是实现FLOYD算法求解最短路经。

首先对于图的创建选择合适的存储结构进行存储，对于合适的存储结构可以简化程序。

本实验采用邻接矩阵存储。

然后是实现FLOYD算法求解最短路经，在FLOYD算法中路径的长度即是图中两定点间边的权值，FLOYD算法要求输出任意两个顶点间的最短路径，而且经过的顶点也要输出。

考虑到问题的特殊性，采用一个二维数组和一个三维数组进行存储。

二维数组存储最短路径，三维数组存储路径经过的顶点，在进行适当的算法后对这两个数组进行输出即可。

通过问题的分解，逐个解决，事先所要求的程序。

最短路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。

传统的最短路径算法主要有Floyd算法和Dijkstra算法。

Floyd算法用于计算所有结点之间的最短路径。

Dijkstra算法则用于计算一个结点到其他所有结点的最短路径。

Dijkstra算法是已经证明的能得出最短路径的最优解，但它的效率是一个很大的问题。

对于具有n个结点的一个图，计算一个结点到图中其余结点最短路径的算法时间复杂度为O(n2)。

对于一座大中型城市，地理结点数目可能达到几万个到几十万个，计算最短路径的时间开销将是非常巨大的。

本文根据吴一民老师的建议，分析当前存在的各种求最短路径的算法，提出一种新的基于层次图的最短路径算法，即将一个平面图划分若干子图，子图抽象为一个高层图。

最短路径的计算首先在高层图中进行，缩小了最短路径的查找范围，降低了最短路径计算的时间开销。

实现图的最短路径算法（Python）图的最短路径算法是解决图中两个节点之间最短路径问题的方法。

在图中，节点之间可以通过边相连，并且每条边都有一个权重或距离值。

最短路径算法可以找到从起始节点到目标节点的最短路径，并计算出该路径上所有边权重的总和。

在实现图的最短路径算法之前，我们首先需要建立图的数据结构。

图可以通过邻接矩阵或邻接表来表示。

邻接矩阵是一个二维矩阵，其中矩阵的行和列代表图中的节点，矩阵中的元素表示节点之间的边的权重。

邻接表是一个字典，其中每个节点都与它的邻居节点列表相关联，列表中的元素表示节点之间的边的权重。

在Python中，我们可以使用字典和列表来实现图的邻接表表示。

首先，我们创建一个Graph类来表示图，并定义一些必要的方法。

以下是一个图类的示例实现：```pythonclass Graph:def __init__(self):self.nodes = set()self.edges = {}def add_node(self, node):self.nodes.add(node)def add_edge(self, from_node, to_node, weight):if from_node not in self.edges:self.edges[from_node] = {}self.edges[from_node][to_node] = weightdef get_neighbors(self, node):return self.edges[node]```在Graph类中，我们使用一个nodes集合来存储图中的节点，并使用一个edges字典来存储从一个节点到其他节点的边的权重。

add_node方法用于添加节点到图中，add_edge方法用于添加边的权重，get_neighbors方法用于获取一个节点的所有邻居节点及对应的边的权重。

接下来，我们可以通过实现最短路径算法来找到从起始节点到目标节点的最短路径。

问题描述：若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。

试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。

基本要求：（1）从文件中读入有向网中顶点的数量和顶点间的票价的矩阵。

（2）以用户指定的起点和终点，输出从起点到终点的花费。

一、需求分析：1、本程序需要用矩阵来存储图的各种信息。

2、测试数据输入（文件）5－1 10 3 20 －1－1 －1 －1 5 －1－1 2 －1 －1 15－1 －1 －1 －1 11－1 －1 －1 －1 －1（用户）起点 0终点 4输出18实现提示：（1）设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）。

（2）此题为求有向网中顶点间最短路径问题，可建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度。

（3） Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度。

因为每次都要在D中找最小值，为提高性能，用最小值堆的优先队列存储D值。

（4）考虑没有路径时的输出。

二、概要设计：抽象数据类型：为实现上述功能需建立一个二维数组和图类。

算法的基本思想：1、图的信息的读取：定义一个二维数组，将图的信息读入，并将两边距离为-1的边转换为一个较大的数（>>途中各点之间的距离）。

2、Dijkstra算法：根据输入的第一个结点首先找到（直接距离）该点最近的A，则这两点之间的边是必须的，然后比较通过A到其他点的距离l1和直接到其他点的距离l2。

如果l1<l2，则用l1的距离替换l2。

重复上述操作n-1（n为结点数）次。

得到的即为第一个结点到其他结点的最短距离。

程序的流程程序由三个模块组成：输入模块：读入图的信息（用矩阵进行存储）。

处理模块：Dijkstra算法。

图的最短路径算法的实现前言在图论中，最短路径问题是一类比较经典的问题，例如求出从A到B的最短路径。

在实际应用中，比如路线规划等领域，最短路径算法也有着广泛的应用。

本文主要介绍了几种常见的图的最短路径算法，并对其实现进行了简要的介绍，并提供了具体的代码实现。

最短路径问题在图论中，最短路径问题是指在加权图中寻找两个节点之间所有路径中权值和最小的路径。

最短路径问题可以分为单源最短路径问题和全源最短路径问题。

单源最短路径问题单源最短路径问题是指在加权图中，给定一个起点，求其到图中各个点的最短路径。

其中比较经典的算法有：Dijkstra算法Dijkstra算法是一种比较经典的单源最短路径算法，它通过构建一个最短路径树来求解问题。

Dijkstra算法的思路是：1.首先创建一个长度为V的数组dist，表示源点到其他所有顶点的距离，初始化为∞，源点到源点的距离为0。

2.创建一个长度为V的数组visited，表示目前得到最短路径的顶点，初始化为false。

3.从dist数组中选择最小的一个顶点，将它标记为visited。

4.对于每个未标记的相邻顶点，计算通过该顶点到源点的距离，如果该距离比之前的估计距离小，则更新该顶点的距离。

5.重复步骤3和4，直到目标顶点被标记为visited，或者剩余的顶点中没有可以到达的点为止。

Dijkstra算法应用较为广泛，但是它有两个局限性，第一个是它只能够处理边权值为非负数的图。

另一个局限性则是，它无法处理有负权边的情况，如果存在负权边，则需要使用一些其他的算法，例如SPFA算法。

下面是Dijkstra算法的实现代码：def dijkstra(graph, src, dest):dist = {i: float('inf') for i in graph}dist[src] =0visited = {}while True:visited[src] = dist[src]if src == dest:breakfor vertex, weight in graph[src].items():if vertex not in visited:new_dist = dist[src] + weightif new_dist < dist[vertex]:dist[vertex] = new_distmin_vertex =Nonefor vertex in graph:if vertex not in visited:if min_vertex is None:min_vertex = vertexelif dist[vertex] < dist[min_vertex]:min_vertex = vertexif min_vertex is None:breaksrc = min_vertexreturn visited[dest]Bellman-Ford算法Bellman-Ford算法也是一种常见的单源最短路径算法，它能够处理边权值为负数的情况。

【数据结构算法】实验8-图的最短路径问题（附源代码）浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验八图的最短路径问题实验成绩指导老师（签名）日期一.实验目的和要求1.掌握图的最短路径概念。

2.理解并能实现求最短路径的DijKstra算法（用邻接矩阵表示图）。

二. 实验内容1、编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，基本操作包括：① 初始化邻接矩阵表示的有向带权图void InitMatrix(adjmatrixG);② 建立邻接矩阵表示的有向带权图 void CreateMatrix(adjmatrix G, int n) （即通过输入图的每条边建立图的邻接矩阵）;③ 输出邻接矩阵表示的有向带权图void PrintMatrix(adjmatrix G, int n) （即输出图的每条边）。

把邻接矩阵的结构定义以及这些基本操作函数存放在头文件Graph2.h中。

2、编写求最短路径的DijKstra算法函数 void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n) ，该算法求从顶点i到其余顶点的最短路径与最短路径长度，并分别存于数组path 和dist 中。

编写打印输出从源点到每个顶点的最短路径及长度的函数void PrintPath(int dist[], edgenode *path[], int n)。

3、编写测试程序（即主函数），首先建立并输出有向带权图，然后计算并输出从某顶点v0到其余各顶点的最短路径。

要求：把指针数组的基类型结构定义edgenode、求最短路径的DijKstra算法函数、打印输出最短路径及长度的函数PrintPath以及主函数存放在文件test9_2.cpp中。

测试数据如下：4、填写实验报告，实验报告文件取名为report8.doc。

5、上传实验报告文件report8.doc与源程序文件test9_2.cpp及Graph2.h到Ftp服务器上自己的文件夹下。