一、定義

在圖中，求兩個(gè)不同頂點(diǎn)間的不同路徑中，邊的權(quán)值和最小的那條路徑。這條路徑就叫做最短路徑（Shortest Path）,第一個(gè)頂點(diǎn)叫做源點(diǎn)（Source）,最后一個(gè)頂點(diǎn)叫做終點(diǎn)（Destination）。

二、分類

單源最短路徑問題：從某固定源點(diǎn)出發(fā)，求其到所有其他頂點(diǎn)的最短路徑。

? ? ? ? 包括有權(quán)圖和無權(quán)圖

多源最短路徑問題：求任意兩頂點(diǎn)間的最短路徑。

三、算法

1、UNweighted();解決無權(quán)圖單源最短路徑問題。

首先需要解決無權(quán)圖的單源最短路經(jīng)問題：用BFS（廣度優(yōu)先搜索）的思想，從源點(diǎn)開始一層一層找出到各頂點(diǎn)的最短路徑（逐一增加1），用數(shù)組dist[]存放每個(gè)頂點(diǎn)的最短路徑長度，用數(shù)組path[]存放最短路徑的前驅(qū)頂點(diǎn)，終點(diǎn)的最短路徑就等于該路徑上終點(diǎn)的前驅(qū)頂點(diǎn)的最短路徑加上到終點(diǎn)邊上的權(quán)重。無權(quán)圖可看做每條邊權(quán)重均為1的有權(quán)圖。

2、Dijkstra();解決有權(quán)圖單源最短路徑問題。

掌握了無權(quán)圖的單源最短路徑算法的基礎(chǔ)上，用在有權(quán)圖上會(huì)發(fā)現(xiàn)最短路徑不再是經(jīng)過頂點(diǎn)的數(shù)量，而是路徑上各條邊權(quán)重的和。 也就是，從源點(diǎn)開始逐層掃描各頂點(diǎn)的最短路徑，第n層頂點(diǎn)的最短路徑可能因n+1層頂點(diǎn)的邊上的權(quán)重而改變。例如：v1→v6，掃描至第一層v1→v4，最短路徑為1，掃描至第二層，v1→v4→v6，最短路徑為1+8=9；當(dāng)掃描至第三層會(huì)發(fā)現(xiàn)v1→v4→v7→v6這條路徑的權(quán)重和為1+4+1=6，改變了v1→v6的最短路徑。解決方法為，逐層找出該層中路徑最短的頂點(diǎn)Vi，Vi的路徑長度確定，且為最短。同時(shí)影響前一層各頂點(diǎn)的路徑長度。

Dijkstra算法算逐層找到該層中最短路徑的頂點(diǎn)Vi，通過Vi更新鄰接點(diǎn)的最短路徑，找到最后一層后這個(gè)連通集內(nèi)所有的頂點(diǎn)的最短路徑均已確定。不在同一個(gè)連通分量內(nèi)的頂點(diǎn)用最大值表示不連通。（拒絕負(fù)權(quán)邊）

?3、Floyd();Floyd算法又稱為插點(diǎn)法，是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法，與Dijkstra算法類似。

百度百科和CSDN里面，有對(duì)這個(gè)算法很專業(yè)解釋，我看不太明白。

我理解的這個(gè)算法就是——挨個(gè)試。

用二維數(shù)組儲(chǔ)存多源最短路徑，任意兩個(gè)頂點(diǎn)i、j，通過任意頂點(diǎn)k，如果能縮短路徑，那就更新最短路徑。也就是? ?if(dist[i][k]+dist[k][j]<dist[i][j])? ?dist[i][j]=dist[i][k]+dist[k][j] .三個(gè)任意，也就是三個(gè)for循環(huán)。

圖片來源：參考文章傳送門——圖的最短路徑算法-Floyd算法-弗洛伊德算法 - 騰訊云開發(fā)者社區(qū)-騰訊云

四、代碼

鄰接表適合用于稀疏圖；鄰接矩陣適合用于稠密圖。

lgraph.h?

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

/*聲明圖的一些要素*/
#define MaxVertexNum 100
typedef int Vertex;				//頂點(diǎn)類型 
typedef int WeighType;			//權(quán)重類型 
typedef char VertexData;		//頂點(diǎn)數(shù)據(jù) 
typedef struct toadjv{			//鄰接表結(jié)構(gòu)體 
	Vertex v;
	WeighType weigh;
	struct toadjv *next;
}PtrToAdjv;

typedef struct vertex_node{		//頂點(diǎn)結(jié)構(gòu)體 
	PtrToAdjv *firstedge;		//指向鄰接表 
	VertexData data;
}AdjList; 						

typedef struct graph_node{		//聲明圖結(jié)構(gòu)體 
	int VertexNum;
	int EdgeNum;
	AdjList G[MaxVertexNum];	//頂點(diǎn)數(shù)組 
}LGraph;

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

typedef struct edge_node{		//邊結(jié)構(gòu)體，主要方便插入操作 
	Vertex v1,v2;
	WeighType weigh;
}Edge;

/*建圖 鄰接表*/
LGraph *init_graph(int VertexNum);				//初始化有VertexNum個(gè)頂點(diǎn)的圖 
void insert_edge(LGraph *pGraph,Edge *pEdge);	//向圖中插入邊 
LGraph *biuld_graph(int VertexNum);				//建圖 

/*建圖 鄰接矩陣*/
MGraph *init_mgraph(int VertexNum);				//初始化有VertexNum個(gè)頂點(diǎn)的圖（鄰接矩陣）
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);				//鄰接矩陣 

/*隊(duì)列，廣度優(yōu)先遍歷使用*/
#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);				//迪杰斯特拉算法，解決有權(quán)圖的單源最短路徑問題 
void Floyd(MGraph *pGraph);							//弗洛伊德算法，解決有權(quán)圖的多源最短路徑問題 
#endif

lgraph.c?

#include "lgraph.h"
/*初始化一個(gè)有VertexNum個(gè)頂點(diǎn)的圖*/
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++){				//方便起見，用循環(huán)把每個(gè)頂點(diǎn)鏈接 
		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++){				//方便起見，用循環(huán)把每個(gè)頂點(diǎn)鏈接 
		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;
	}
}
/*深度優(yōu)先遍歷*/
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);
		}
	}
}
/*廣度優(yōu)先遍歷*/
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);
}
/*隊(duì)列相關(guān)函數(shù)*/
Que *init_queue(){									//生成隊(duì)列 
	Que *pQ=(Que*)malloc(sizeof(Que));
	pQ->head=pQ->rear=NULL;
	return pQ;
}
int isempty_queue(Que *pQ){							//隊(duì)列判空 
	return pQ->head==NULL;
}
void in_queue(Que *pQ,Element data){				//入隊(duì) 
	Qnode *pQnode=(Qnode*)malloc(sizeof(Qnode));
	pQnode->data=data;
	pQnode->next=NULL;
	if(isempty_queue(pQ)){							//需要注意隊(duì)空情況 
		pQ->head=pQ->rear=pQnode;
	}else{
		pQ->rear->next=pQnode;
		pQ->rear=pQnode;
	}
}
Element out_queue(Que *pQ){							//出隊(duì) 
	Element temp=ERROR;
	if(!isempty_queue(pQ)){
		temp=pQ->head->data;
		Qnode *ptemp=pQ->head;
		pQ->head=pQ->head->next;
		if(pQ->head==NULL) 							//同樣需要注意隊(duì)空情況 
			pQ->rear=NULL;
		free(ptemp);
	}
	return temp;
}

/*無權(quán)圖單源最短路徑算法*/
Vertex path[MaxVertexNum]; 							//用數(shù)組保存最短路徑中下標(biāo)頂點(diǎn)的前一個(gè)頂點(diǎn) 
int dist[MaxVertexNum];								//用數(shù)組保存源點(diǎn)到其他頂點(diǎn)的最短路徑 
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){			//無權(quán)圖的單源最短路徑 
	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);
	}
}
/*有權(quán)圖的單源最短路徑*/
/*杰斯特拉算法，解決有權(quán)圖的單源最短路徑問題。整體思想是：利用BFS的思路，逐層解決。
首先訪問源點(diǎn)visited[v0]=1，將第一層每個(gè)頂點(diǎn)的路徑保存在數(shù)組dist[]中，找到第一層頂點(diǎn)中的最短路徑mindist和頂點(diǎn)minv，visited[minv]標(biāo)記確定；
其次訪問minv，同時(shí)將第二層每個(gè)未標(biāo)記確定的頂點(diǎn)的最短路徑保存在數(shù)組dist[]中，找出最小值mindist和頂點(diǎn)minv,確定第二層的minv，以此類推可以將
一個(gè)連通分量里面所有頂點(diǎn)的最短路徑確定。而其他連通分量與源點(diǎn)因?yàn)槲催B通，最短路徑為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;							//初始化已確定最短路徑長度的頂點(diǎn)，均為0表示均為確定 
		dist[v]=MaxPathFlag;
        path[v]=-1;
	}
	dist[v]=0;									//初始化起點(diǎn)的最短路徑為0 
	while(!visited[v]){							//當(dāng)所有點(diǎn)均已標(biāo)記，循環(huán)退出 
		visited[v]=1;							//標(biāo)記已確定最短路徑的頂點(diǎn)v 
		for(PtrToAdjv *p=pGraph->G[v].firstedge;p;p=p->next){
/*通過v，如果有其他頂點(diǎn)的最短路徑更短，更新。本質(zhì)上是更新了v的鄰接點(diǎn)的長度*/
			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++){//找出下一個(gè)最短路徑的頂點(diǎn)v 
			if(dist[v]<mindist&&visited[v]==0){	//掃描未標(biāo)記的頂點(diǎn)中的最短路徑，確定下一個(gè)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文章來源地址http://www.zghlxwxcb.cn/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;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——圖的最短路徑的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！