数据结构——图的最短路径

这篇具有很好参考价值的文章主要介绍了数据结构——图的最短路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、定义

在图中,求两个不同顶点间的不同路径中,边的权值和最小的那条路径。这条路径就叫做最短路径(Shortest Path),第一个顶点叫做源点(Source),最后一个顶点叫做终点(Destination)

二、分类

单源最短路径问题:从某固定源点出发,求其到所有其他顶点的最短路径。

        包括有权图和无权图

多源最短路径问题:求任意两顶点间的最短路径。

三、算法

1、UNweighted();解决无权图单源最短路径问题。

首先需要解决无权图的单源最短路经问题:用BFS(广度优先搜索)的思想,从源点开始一层一层找出到各顶点的最短路径(逐一增加1),用数组dist[]存放每个顶点的最短路径长度,用数组path[]存放最短路径的前驱顶点,终点的最短路径就等于该路径上终点的前驱顶点的最短路径加上到终点边上的权重。无权图可看做每条边权重均为1的有权图。

最短路径问题数据结构,数据结构,c语言,图论
引用自中国大学慕课数据结构——陈越老师

2、Dijkstra();解决有权图单源最短路径问题。

掌握了无权图的单源最短路径算法的基础上,用在有权图上会发现最短路径不再是经过顶点的数量,而是路径上各条边权重的和。 也就是,从源点开始逐层扫描各顶点的最短路径,第n层顶点的最短路径可能因n+1层顶点的边上的权重而改变。例如:v1→v6,扫描至第一层v1→v4,最短路径为1,扫描至第二层,v1→v4→v6,最短路径为1+8=9;当扫描至第三层会发现v1→v4→v7→v6这条路径的权重和为1+4+1=6,改变了v1→v6的最短路径。解决方法为,逐层找出该层中路径最短的顶点Vi,Vi的路径长度确定,且为最短。同时影响前一层各顶点的路径长度。

Dijkstra算法算逐层找到该层中最短路径的顶点Vi,通过Vi更新邻接点的最短路径,找到最后一层后这个连通集内所有的顶点的最短路径均已确定。不在同一个连通分量内的顶点用最大值表示不连通。(拒绝负权边)

最短路径问题数据结构,数据结构,c语言,图论
引用自中国大学慕课数据结构——陈越老师

 3、Floyd();Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。

百度百科和CSDN里面,有对这个算法很专业解释,我看不太明白。

我理解的这个算法就是——挨个试。

用二维数组储存多源最短路径,任意两个顶点i、j,通过任意顶点k,如果能缩短路径,那就更新最短路径。也就是   if(dist[i][k]+dist[k][j]<dist[i][j])   dist[i][j]=dist[i][k]+dist[k][j] .三个任意,也就是三个for循环。

最短路径问题数据结构,数据结构,c语言,图论

最短路径问题数据结构,数据结构,c语言,图论

最短路径问题数据结构,数据结构,c语言,图论

图片来源:参考文章传送门——图的最短路径算法-Floyd算法-弗洛伊德算法 - 腾讯云开发者社区-腾讯云

四、代码

邻接表适合用于稀疏图;邻接矩阵适合用于稠密图。

lgraph.h 

#ifndef LGRAPH_H
#define LGRAPH_H
#include <stdio.h>
#include <stdlib.h>

/*声明图的一些要素*/
#define MaxVertexNum 100
typedef int Vertex;				//顶点类型 
typedef int WeighType;			//权重类型 
typedef char VertexData;		//顶点数据 
typedef struct toadjv{			//邻接表结构体 
	Vertex v;
	WeighType weigh;
	struct toadjv *next;
}PtrToAdjv;

typedef struct vertex_node{		//顶点结构体 
	PtrToAdjv *firstedge;		//指向邻接表 
	VertexData data;
}AdjList; 						

typedef struct graph_node{		//声明图结构体 
	int VertexNum;
	int EdgeNum;
	AdjList G[MaxVertexNum];	//顶点数组 
}LGraph;

/*邻接矩阵*/
typedef struct mgraph_node{
	int VertexNum;
	int EdgeNum;
	WeighType graph[MaxVertexNum][MaxVertexNum];
}MGraph;

typedef struct edge_node{		//边结构体,主要方便插入操作 
	Vertex v1,v2;
	WeighType weigh;
}Edge;

/*建图 邻接表*/
LGraph *init_graph(int VertexNum);				//初始化有VertexNum个顶点的图 
void insert_edge(LGraph *pGraph,Edge *pEdge);	//向图中插入边 
LGraph *biuld_graph(int VertexNum);				//建图 

/*建图 邻接矩阵*/
MGraph *init_mgraph(int VertexNum);				//初始化有VertexNum个顶点的图(邻接矩阵)
void minsert_edge(MGraph *pGraph,Edge *pEdge);	//向图中插入边 
MGraph *biuld_mgraph(int VertexNum);			//建图 

/*遍历*/
void init_visited(int VertexNum);
void DFS(LGraph *pGraph,Vertex v);				//邻接表 
void MDFS(MGraph *pGraph,Vertex v);				//邻接矩阵 
void BFS(LGraph *pGraph,Vertex v);				//邻接表 
void MBFS(MGraph *pGraph,Vertex v);				//邻接矩阵 

/*队列,广度优先遍历使用*/
#define ERROR MaxVertexNum
typedef Vertex Element;
typedef struct queue_node{
	Element data;
	struct queue_node *next;
}Qnode;

typedef struct queue{
	Qnode *head;
	Qnode *rear;
}Que;
Que *init_queue();
int isempty_queue(Que *pQ);
void in_queue(Que *pQ,Element data);
Element out_queue(Que *pQ);

/*单源最短路径*/
#define MaxPathFlag 65535
void init_path(int VertexNum);						//初始化最短路径 
void init_dist(int VertexNum);						//初始化最短路径长度 
void UNweighted(LGraph *pGraph,Vertex v);			//单源最短路径算法
void Dijkstra(LGraph *pGraph,Vertex v);				//迪杰斯特拉算法,解决有权图的单源最短路径问题 
void Floyd(MGraph *pGraph);							//弗洛伊德算法,解决有权图的多源最短路径问题 
#endif

lgraph.c 

#include "lgraph.h"
/*初始化一个有VertexNum个顶点的图*/
LGraph *init_graph(int VertexNum){ 
	LGraph *pGraph=(LGraph*)malloc(sizeof(LGraph));
	pGraph->EdgeNum=0;
	pGraph->VertexNum=VertexNum;
	for(Vertex v=0;v<VertexNum;v++){
		pGraph->G[v].firstedge=NULL;
	}
	return pGraph;
}
MGraph *init_mgraph(int VertexNum){		//邻接矩阵 
	MGraph *pGraph=(MGraph*)malloc(sizeof(MGraph));
	pGraph->VertexNum=VertexNum;
	pGraph->EdgeNum=0;
	for(Vertex v=0;v<VertexNum;v++){
		for(Vertex w=0;w<VertexNum;w++){
			if(v!=w){
				pGraph->graph[v][w]=MaxPathFlag;
			}else{
				pGraph->graph[v][w]=0;
			}
		}
	}
	return pGraph;
} 
/*向图中插入边*/
void insert_edge(LGraph *pGraph,Edge *pEdge){		//邻接表 
	PtrToAdjv *ptrtoadjv=(PtrToAdjv*)malloc(sizeof(PtrToAdjv));
	ptrtoadjv->v=pEdge->v2;
	ptrtoadjv->weigh=pEdge->weigh;
	ptrtoadjv->next=pGraph->G[pEdge->v1].firstedge;
	pGraph->G[pEdge->v1].firstedge=ptrtoadjv;
	/*无向图需要反向链接*/
	PtrToAdjv *ptrtoadjv1=(PtrToAdjv*)malloc(sizeof(PtrToAdjv));
	ptrtoadjv1->v=pEdge->v1;
	ptrtoadjv1->weigh=pEdge->weigh;
	ptrtoadjv1->next=pGraph->G[pEdge->v2].firstedge;
	pGraph->G[pEdge->v2].firstedge=ptrtoadjv1;
	free(pEdge);
}
void minsert_edge(MGraph *pGraph,Edge *pEdge){		//邻接矩阵 
	pGraph->graph[pEdge->v1][pEdge->v2]=pEdge->weigh;
	pGraph->graph[pEdge->v2][pEdge->v1]=pEdge->weigh;//无向图反向链接
	pGraph->EdgeNum+=2;
	free(pEdge); 
} 
/*建图*/
LGraph *biuld_graph(int VertexNum){					//邻接表 
	LGraph *pGraph=init_graph(VertexNum);
	for(Vertex v=0;v<VertexNum;v++){				//方便起见,用循环把每个顶点链接 
		Edge *pEdge=(Edge*)malloc(sizeof(Edge));
		pEdge->v1=v;pEdge->v2=v+1;
		if(v+1==VertexNum) pEdge->v2=0;
		pEdge->weigh=v+1;			
		insert_edge(pGraph,pEdge);
	}
	return pGraph;
}
MGraph *biuld_mgraph(int VertexNum){				//邻接矩阵
	MGraph *pGraph=init_mgraph(VertexNum);
	for(Vertex v=0;v<VertexNum;v++){				//方便起见,用循环把每个顶点链接 
		Edge *pEdge=(Edge*)malloc(sizeof(Edge));
		pEdge->v1=v;pEdge->v2=v+1;
		if(v+1==VertexNum) pEdge->v2=0;
		pEdge->weigh=v+1;
		minsert_edge(pGraph,pEdge);
	}
	return pGraph;
}
/*声明全局变量,判断访问记录,主要用于DFS算法和BFS算法*/
int visited[MaxVertexNum];							//用来判断是否已访问过
void init_visited(int VertexNum){					//初始化访问记录 
	for(Vertex v=0;v<VertexNum;v++){
		visited[v]=0;
	}
}
/*深度优先遍历*/
void DFS(LGraph *pGraph,Vertex v){
	visited[v]=1;
	printf("%d ",v);
	for(PtrToAdjv *w=pGraph->G[v].firstedge;w;w=w->next){
		if(visited[w->v]==0){
			DFS(pGraph,w->v);
		}
	}
}
void MDFS(MGraph *pGraph,Vertex v){					//邻接矩阵 
	visited[v]=1;
	printf("%d ",v);
	for(Vertex w=0;w<pGraph->VertexNum;w++){
		if(visited[w]==0&&pGraph->graph[v][w]<MaxPathFlag){
			MDFS(pGraph,w);
		}
	}
}
/*广度优先遍历*/
void BFS(LGraph *pGraph,Vertex v){
	Que *pQ=init_queue();
	visited[v]=1;
	printf("%d ",v);
	in_queue(pQ,v);
	while(!isempty_queue(pQ)){
		v=out_queue(pQ);
		for(PtrToAdjv *w=pGraph->G[v].firstedge;w;w=w->next){
			if(visited[w->v]==0){
				visited[w->v]=1;
				printf("%d ",w->v);
				in_queue(pQ,w->v);
			}
		}
	}
	free(pQ);
}
void MBFS(MGraph *pGraph,Vertex v){					//邻接矩阵 
	Que *pQ=init_queue();
	visited[v]=1;
	printf("%d ",v);
	in_queue(pQ,v);
	while(!isempty_queue(pQ)){
		v=out_queue(pQ);
		for(Vertex w=0;w<pGraph->VertexNum;w++){
			if(visited[w]==0&&pGraph->graph[v][w]<MaxPathFlag){
				visited[w]=1;
				printf("%d ",w);
				in_queue(pQ,w);
			}
		}
	}
	free(pQ);
}
/*队列相关函数*/
Que *init_queue(){									//生成队列 
	Que *pQ=(Que*)malloc(sizeof(Que));
	pQ->head=pQ->rear=NULL;
	return pQ;
}
int isempty_queue(Que *pQ){							//队列判空 
	return pQ->head==NULL;
}
void in_queue(Que *pQ,Element data){				//入队 
	Qnode *pQnode=(Qnode*)malloc(sizeof(Qnode));
	pQnode->data=data;
	pQnode->next=NULL;
	if(isempty_queue(pQ)){							//需要注意队空情况 
		pQ->head=pQ->rear=pQnode;
	}else{
		pQ->rear->next=pQnode;
		pQ->rear=pQnode;
	}
}
Element out_queue(Que *pQ){							//出队 
	Element temp=ERROR;
	if(!isempty_queue(pQ)){
		temp=pQ->head->data;
		Qnode *ptemp=pQ->head;
		pQ->head=pQ->head->next;
		if(pQ->head==NULL) 							//同样需要注意队空情况 
			pQ->rear=NULL;
		free(ptemp);
	}
	return temp;
}

/*无权图单源最短路径算法*/
Vertex path[MaxVertexNum]; 							//用数组保存最短路径中下标顶点的前一个顶点 
int dist[MaxVertexNum];								//用数组保存源点到其他顶点的最短路径 
void init_path(int VertexNum){						//初始化最短路径 
	for(Vertex v=0;v<VertexNum;v++){
		path[v]=-1;
	}
}
void init_dist(int VertexNum){						//初始化最短路径长度
	for(Vertex v=0;v<VertexNum;v++){
		dist[v]=-1;
	}
}
void UNweighted(LGraph *pGraph,Vertex v){			//无权图的单源最短路径 
	init_path(pGraph->VertexNum);
	init_dist(pGraph->VertexNum);
	Vertex tempv=v;
	Que *pQ=init_queue();
	dist[v]=0;
	in_queue(pQ,v);
	while(!isempty_queue(pQ)){
		v=out_queue(pQ);
		for(PtrToAdjv *p=pGraph->G[v].firstedge;p;p=p->next){
			if(dist[p->v]==-1){
				dist[p->v]=dist[v]+1;
				path[p->v]=v;
				in_queue(pQ,p->v);
			}
		}
	}
	for(Vertex v=0;v<pGraph->VertexNum;v++){
		printf("%d ",dist[v]);
		if(v==pGraph->VertexNum-1) printf("\n");
	}
	scanf("%d",&v);
	while(v!=tempv){
		printf("%d ",v);
		v=path[v];
		if(v==tempv) printf("%d\n",tempv);
	}
}
/*有权图的单源最短路径*/
/*杰斯特拉算法,解决有权图的单源最短路径问题。整体思想是:利用BFS的思路,逐层解决。
首先访问源点visited[v0]=1,将第一层每个顶点的路径保存在数组dist[]中,找到第一层顶点中的最短路径mindist和顶点minv,visited[minv]标记确定;
其次访问minv,同时将第二层每个未标记确定的顶点的最短路径保存在数组dist[]中,找出最小值mindist和顶点minv,确定第二层的minv,以此类推可以将
一个连通分量里面所有顶点的最短路径确定。而其他连通分量与源点因为未连通,最短路径为MaxDist,表示不存在路径。 
*/

void Dijkstra(LGraph *pGraph,Vertex v){
	int dist[pGraph->VertexNum];				
	int visited[pGraph->VertexNum];
    Vertex path[pGraph->VertexNum];
	for(Vertex v=0;v<pGraph->VertexNum;v++){	//初始化最短路径长度为MaxPathFlag,表示未连通 
		visited[v]=0;							//初始化已确定最短路径长度的顶点,均为0表示均为确定 
		dist[v]=MaxPathFlag;
        path[v]=-1;
	}
	dist[v]=0;									//初始化起点的最短路径为0 
	while(!visited[v]){							//当所有点均已标记,循环退出 
		visited[v]=1;							//标记已确定最短路径的顶点v 
		for(PtrToAdjv *p=pGraph->G[v].firstedge;p;p=p->next){
/*通过v,如果有其他顶点的最短路径更短,更新。本质上是更新了v的邻接点的长度*/
			if(dist[p->v]>dist[v]+p->weigh&&!visited[p->v]){
                dist[p->v]=dist[v]+p->weigh;
                path[p->v]=v;
            }   
		}
		Vertex minv;
		int mindist=MaxPathFlag;
		for(Vertex v=0;v<pGraph->VertexNum;v++){//找出下一个最短路径的顶点v 
			if(dist[v]<mindist&&visited[v]==0){	//扫描未标记的顶点中的最短路径,确定下一个v 
				mindist=dist[v];
				minv=v;
			}
		}
		v=minv;
	}
	for(Vertex v=0;v<pGraph->VertexNum;v++){
		printf("%d ",dist[v]);
	}
}
void Floyd(MGraph *pGraph){
	WeighType dist[pGraph->VertexNum][pGraph->VertexNum];
	Vertex    path[pGraph->VertexNum][pGraph->VertexNum];
	for(Vertex v=0;v<pGraph->VertexNum;v++){
		for(Vertex w=0;w<pGraph->VertexNum;w++){
			if(v!=w) dist[v][w]=pGraph->graph[v][w];
			else dist[v][w]=0;
			path[v][w]=-1;
		}
	}
	for(Vertex k=0;k<pGraph->VertexNum;k++){
		for(Vertex i=0;i<pGraph->VertexNum;i++){
			for(Vertex j=0;j<pGraph->VertexNum;j++){
				if(dist[i][k]+dist[k][j]<dist[i][j]){
					dist[i][j]=dist[i][k]+dist[k][j];
					if(i!=j) path[i][j]=k;
					else path[i][j]=-1;
				}
			}
		}
	}
	for(Vertex i=0;i<pGraph->VertexNum;i++){
		for(Vertex j=0;j<pGraph->VertexNum;j++){
			printf("%4d",dist[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	for(Vertex i=0;i<pGraph->VertexNum;i++){
		for(Vertex j=0;j<pGraph->VertexNum;j++){
			printf("%4d",path[i][j]);
		}
		printf("\n");
	}
	
} 

main.c文章来源地址https://www.toymoban.com/news/detail-768006.html

#include <stdio.h>
#include <stdlib.h>
#include "lgraph.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[]) {
	int VertexNum;
	scanf("%d",&VertexNum);
	LGraph *pGraph=biuld_graph(VertexNum);
	init_visited(VertexNum);
	DFS(pGraph,4);printf("\n");
	init_visited(VertexNum);
	BFS(pGraph,0);printf("\n");
	UNweighted(pGraph,9);
	Dijkstra(pGraph,0);


//	MGraph *pGraph=biuld_mgraph(VertexNum);
//	init_visited(VertexNum);
//	MDFS(pGraph,4);printf("\n\n");
//	init_visited(VertexNum);
//	MBFS(pGraph,0);printf("\n\n");
//	Floyd(pGraph);
	return 0;
}

到了这里,关于数据结构——图的最短路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图的最短路径 (数据结构实验报告)

    一、实验目的 讲清楚进行本实验后要学到的知识、掌握的数据结构及其定义和表示方法,讲清楚所采用的算法。 掌握图结构的(邻接矩阵)输入方法 掌握图结构的说明、创建以及图的存储表示(邻接矩阵) 掌握最短路径算法原理 掌握最短路径算法的编程实现方法 二、实验

    2024年02月06日
    浏览(46)
  • 数据结构实验任务六 :基于 Dijsktra 算法的最短路径求解

    本次代码为实验六:基于 Dijsktra 算法的最短路径求解实现。本实验的重点在于对于Dijsktra算法的理解。有关Dijsktra的资料可以参考有关博文: 图论:Dijkstra算法——最详细的分析,图文并茂,一次看懂!-CSDN博客 以下附上实现代码: 以上代码仅供参考,欢迎交流。

    2024年02月04日
    浏览(46)
  • java数据结构与算法刷题-----LeetCode1091. 二进制矩阵中的最短路径

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 双分裂蛇:是求二维表中从起点到终点的经典思路(也是求无权图的最短路径问题的经典解法)。创建两条分裂蛇,分别从起点和

    2024年04月26日
    浏览(45)
  • 【数据结构】图的应用:最小生成树;最短路径;有向无环图描述表达式;拓扑排序;逆拓扑排序;关键路径

    目录 1、最小生成树 1.1 概念  1.2 普利姆算法(Prim) 1.3 克鲁斯卡尔算法(Kruskal)  2、最短路径 2.1 迪杰斯特拉算法(Dijkstra) 2.2 弗洛伊德算法(Floyd)  2.3 BFS算法,Dijkstra算法,Floyd算法的对比 3、有向无环图描述表达式 3.1 有向无环图定义及特点 3.2 描述表达式 4、拓扑排序

    2024年02月07日
    浏览(46)
  • 算法:关于图的最短路径算法

    本篇总结的是图当中的最短路径算法 单源最短路径问题:给定一个图 G = ( V , E ) G=(V,E)G=(V,E) ,求源结点 s ∈ V s∈Vs∈V 到图中每个结点 v ∈ V v∈Vv∈V 的最短路径。 Dijkstra 算法就适用于解决带权重的有向图上的单源最短路径问题,同时算法要求图中所有边的权重非负。一

    2024年02月19日
    浏览(35)
  • 最小花费-银行转账-图的最短路-超详细解析注释

    最小花费-银行转账-图的最短路-超详细解析注释 【题目描述】 在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问A最少需要多少钱使得转账后B收到100元。 【输入】 第一

    2024年01月20日
    浏览(41)
  • matlab算法模型——图的最短路径和距离

    目录 一、前言 二、最短路径 1.sqarse创建稀疏矩阵 ​​2.有向图的最短路径         使用graphallshortestpaths函数 使用dijkstra.ma函数(直接引用) 3.无向图的最短路径 使用函数graphallshortestpaths(2021的版本不能用了) 使用shortestpath函数 三、未解决的问题 动态规划——求解某类问题

    2024年02月04日
    浏览(34)
  • DS图—图的最短路径(无框架)迪杰斯特拉算法

    目录 题目描述 AC代码 题目描述 给出一个图的邻接矩阵,输入顶点v,用迪杰斯特拉算法求顶点v到其它顶点的最短路径。 输入 第一行输入t,表示有t个测试实例 第二行输入顶点数n和n个顶点信息 第三行起,每行输入邻接矩阵的一行,以此类推输入n行 第i个结点与其它结点如果

    2023年04月08日
    浏览(38)
  • 数据结构:地图着色问题——图的应用——回溯法

    目录 前言 一、解决问题的思路 二、存储结构设计 三、代码 1.创建图函数 2.判断色号是否相同函数 3.回溯函数 4.整体代码 总结 本次解决的问题:用图模拟部分地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少。 先来一张效果图 将邻接矩阵

    2024年02月04日
    浏览(53)
  • 详解图的最短路径算法(BFS、Dijkstra、Floyd)(附上图解步骤)

    最短路径分为两种: (1)单源路径:从某顶点出发,到其他全部顶点的最短路径 (2)顶点间的最短路径:任意两个顶点之间的最短路径 最短路径的结果主要有两个方面: (1)顶点之间最短路径的长度 (2)从源顶点到目标顶点的路径 只有边权为 1 时才能用BFS求最短路。

    2024年02月05日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包