数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

目录

一、最短路径概念

二、迪杰斯特拉(Dijkstra)算法(单源最短路径)

1、原理

2、过程

 3、代码

三、弗洛伊德(Floyd)算法(多源最短路径)

1、原理

2、存储

3、遍历

4、代码

参考资料


 

一、最短路径概念

最短路径,顾名思义,两结点之间最短的路径(可以是非邻接结点)。

最小生成树最短路径区别:

最小生成树连通图最短路径

最短路径:两任意结点之间(可以非邻接)的最短路径

二、迪杰斯特拉(Dijkstra)算法(单源最短路径)

优点:效率较高,时间复杂度为O(n^2)

缺点:只能求一个顶点所有顶点最短路径。 (单源最短路

1、原理

1、先选定一个根结点,并选定一个数组,先确定未遍历前的初始距离,把距离最短的邻接结点选定为中间结点,并标记访问过,开始往下遍历,挨个访问那个中间结点邻接结点。计算出根结点到中间结点+中间结点到新邻接结点的距离,作为新距离,对比新距离和旧距离,如果新距离大,则把新距离替换掉旧距离,否则不变。

2、一轮访问结束后,从未标记的结点选定距离最短的,把它作为中间结点,继续往下访问。若都标记过,则算法结束。

2、过程

 1、保存根结点及到其他结点的权(距离)

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

 2、 访问最近结点作为中间结点数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

3、对比新距离根结点到中间结点+中间结点到新结点)和旧距离根结点直接到新结点) 

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

 4、若新距离短,修改保存到数组

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

 5、继续访问后面的,把未访问的距离根最近结点作为中间结点继续访问它的邻接结点

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

 6、继续对比新距离和旧距离

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

 7、若新距离短,则修改保存到数组

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

 8、 继续以距离根结点最短的结点为对象,访问它的邻接结点数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

 9、全部访问完毕,结束算法

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

欣赏一下自己的稿书: 数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

 3、代码

//迪杰斯特拉(Dijkstra)算法
/*测试案例
ABCDEFGHI
B 1 C 5
A 1 C 3 D 7 E 5
A 5 B 3 E 1 F 7
B 7 E 2 G 3
B 5 C 1 F 3 H 9 G 6 D 2
C 7 E 3 H 5
D 3 E 6 H 2 I 7
F 5 E 9 G 2 I 4
G 7 H 4
*/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

#define MAXSIZE 20
#define MAX 65535					//代表无穷大
int length = 0;							//顶点个数
int root = 0;								//根顶点
int rootDist[MAXSIZE];				//根顶点(记录根到其他顶点的距离)
bool visit[MAXSIZE];				//记录各结点是否访问


//图(顶点和权)
typedef struct
{
	char vertex[MAXSIZE];
	int weight[MAXSIZE][MAXSIZE];			//权可以代替边(自身为0,相连有值,不相连无穷大)
}Graph;
Graph G;


//输入顶点
void InputVertex()
{
	int i;
	char ch;
	printf("请输入图的顶点:\n");
	scanf("%c", &ch);
	for (i = 0; i < MAXSIZE && ch != '\n'; i++)
	{
		G.vertex[i] = ch;
		scanf("%c", &ch);
	}
	length = i;
}

//图权重初始化
void GraphWeightInit()
{
	int i, j;
	for (i = 0; i < length; i++)
	{
		for (j = 0; j < length; j++)
		{
			if (i == j)							//指向自己
				G.weight[i][j] = 0;
			else
				G.weight[i][j] = MAX;	//无穷大
		}
	}
}

//根据数据查找图顶点下标
int FindIndex(char ch)
{
	int i;
	for (i = 0; i < length; i++)
	{
		if (G.vertex[i] == ch)
			return i;
	}
	return -1;
}

//创建图
void CreateGraph()
{
	int i, j, index, weight;
	char ch;
	for (i = 0; i < length; i++)
	{
		printf("请输入%c的邻接顶点及权重(空格分隔,换行结束):\n", G.vertex[i]);
		scanf("%c", &ch);
		while (ch != '\n')
		{
			while (ch == ' ')				//为空格
			{
				scanf("%c", &ch);			//输入字符
				continue;
			}
			index = FindIndex(ch);
			scanf("%d", &weight);		//输入权重
			while (weight == 32)		//32为空格的ASCII码
			{
				scanf("%d", &weight);
				continue;
			}
			G.weight[i][index] = weight;	//存入权重
			scanf("%c", &ch);				//(下一轮)输入字符
		}
	}
}

//根结点初始化
void Init()
{
	int i;
	printf("请输入根结点:\t");
	scanf("%d", &root);
	for (i = 0; i < length; i++)
	{
		rootDist[i] = G.weight[root][i];		//把0作为根,初始化
		visit[i] = false;								//未访问
	}
}

//取最小(在未访问的结点中)
int GetMinInVisit()
{
	int i, min = 0;
	for (i = 0; i < length; i++)
	{
		//未访问
		if (!visit[i])
		{
			//找到最小下标(不能是自身)
			if (rootDist[min] > rootDist[i] || rootDist[min] == 0)
			{
				min = i;
			}
		}
	}
	return min;
}

//检查是否访问完毕
bool IsNull()
{
	bool flag = true;
	for (int i = 0; i < length; i++)
	{
		if (!visit[i])				//还有未访问的
			flag = false;
	}
	return flag;
}

//迪杰斯特拉(Dikstra)算法(生成根到其他顶点的最短路径)
void Dijkstra(int index)
{
	int i;
	visit[index] = true;						//标记访问
	printf("%c %d\t", G.vertex[index], rootDist[index]);

	//遍历中间结点的邻接结点,对比新旧距离
	for (i = 0; i < length; i++)
	{
		//若 旧距离 > 新距离(改变新距离覆盖旧距离)
		if (rootDist[i] > (rootDist[index] + G.weight[index][i]))
		{
			rootDist[i] = rootDist[index] + G.weight[index][i];
		}
	}

	//退出判断
	if (IsNull())
		return;
	index = GetMinInVisit();				//取出最小邻接结点,作为中间结点
	Dijkstra(index);								//递归调用Dijkstra()
}

//输出测试
void Print()
{
	for (int i = 0; i < length; i++)
	{
		printf("\n%c结点邻接结点:\t", G.vertex[i]);
		for (int j = 0; j < length; j++)
		{
			if (G.weight[i][j] != 0 && G.weight[i][j] != MAX)		//有邻接结点
			{
				printf("%c %d\t", G.vertex[j], G.weight[i][j]);
			}
		}
	}
}

int main()
{
	InputVertex();				//输入顶点

	GraphWeightInit();		    //图权重初始化

	CreateGraph();				//创建图

	Init();						//初始化

	Dijkstra(root);				//迪杰斯特拉算法(先以根结点为中间结点遍历)(生成根到其他顶点的最短路径)

	//Print();					//测试输出

	return 0;
}

三、弗洛伊德(Floyd)算法(多源最短路径)

优点:求所有顶点所有顶点最短路径。(多源最短路

缺点:效率较低,时间复杂度为O(n^3)。  

1、原理

基本思想:

不断找点进行中转,比较中转前后最小距离

原理:

最优子结构:图结构中一个显而易见的定理:最短路径的子路径仍然是最短路径 ,这个定理显而易见,比如一条从a到e的最短路径a->b->c->d->e 那么 a->b->c 一定是a到c的最短路径c->d->e一定是c到e的最短路径,反过来,(原理)如果一条最短路必须要经过点k,那么i->k的最短路径+k->j的最短路径一定是i->j 经过k的最短路径因此,最优子结构可以保证

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

(左边矩阵是改进前的,右边矩阵是改进后的。)

弗洛伊德算法定义了两个二维矩阵

D矩阵存放最小权(最短路径)P矩阵存放最短前驱(中转点)

1、矩阵D记录顶点间的最小路径
例如D[1][2]= 3,说明顶点1 到 2 的最短路径为3;
2、矩阵P记录顶点间最小路径中的中转点
例如P[1][2]= 0 说明,1 到 2的最短路径轨迹为:1 -> 0 -> 2。
它通过3重循环,medium为中转点begin为起点end为终点,循环比较D[begin][end] D[begin][medium] + D[medium][end] 之间的最小值,如果(D[begin][medium] + D[medium][end] )为更小值,则把(D[begin][medium] + D[medium][end] )覆盖保存在(D[begin][end])中。

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

2、存储

弗洛伊德算法定义了两个二维矩阵

D矩阵存放最小权(最短路径)P矩阵存放最短前驱(中转点)

 思考:如果求任意两点之间的最短路径,两点之间可以直接到达但却不是最短的路径,要让任意两点(例如从顶点a点到顶点b)之间的路程变短只能引入第三个点(顶点medium)并通过这个顶点medium中转即a->medium->b才可能缩短原来从顶点a点到顶点b的路程。那么这个中转顶点medium是1~n中的哪个点呢?甚至有时候不只通过一个点而是经过两个点或者更多中转点会更短

下面给出一些例子深入理解一下:

:        4 -> 3          一、直接:D[4][3] = 12       二、 过1:D[4][1]+D[1][3]=11   

过1更短,        则D[4][3] = 11        且P[4][3] = P[4][1] = 1

:        1 ->3         一、直接:D[1][3] = 6        二、过2:D[1][2]+D[2][3] = 5

过2更短,        则D[1][3] = 6          且P[1][3] = P[1][2] = 2
数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

 1、假如现在只允许经过1号顶点,求任意两点的最短路径我们应该怎么求呢??

 我们只需要判断 (D[begin][end]) 与 (D[begin][1] + D[1][end]) 的大小。(前者直接到达,后者经历中转)

//只经过1号中转顶点
for (begin = 1; begin <= n; begin++)
    for (end = 1; end <= n; end++)
        if (D[begin][end] > D[begin][1] + D[1][end])
            D[begin][end] = D[begin][1] + D[1][end];

 在只允许经过1号中转顶点的情况下,任意两点之间的路程更新为:

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

2、继续求在只允许经过1和2号两个中转顶点的情况下任意两点之间的最短路程

//只经过1号中转顶点
for (begin = 1; begin <= n; begin++)
    for (end = 1; end <= n; end++)
        if (D[begin][end] > D[begin][1] + D[1][end])
            D[begin][end] = D[begin][1] + D[1][end];


//只经过2号中转顶点
for (begin = 1; begin <= n; begin++)
    for (end = 1; end <= n; end++)
        if (D[begin][end] > D[begin][2] + D[2][end])
            D[begin][end] = D[begin][2] + D[2][end];

在只允许更新1号和2号顶点的情况下,任意两点之间的路径更新为:

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

 3、..........继续往后,运行经过n个中转顶点(即全部)

//运行经过所有中转顶点
for(medium = 0; medium <= n; medium++)
    for (begin = 1; begin <= n; begin++)
        for (end = 1; end <= n; end++)
            if (D[begin][end] > D[begin][medium] + D[medium][end])
                D[begin][end] = D[begin][medium] + D[medium][end];

允许经过所有中转顶点,最后的两点路径更新: 

数据结构与算法(7-4)最短路径(迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法)

3、遍历

//遍历弗洛伊德算法
//确定begin -> end:从最近的前驱开始,一点一点往后追溯
void Traverse_Floyd()
{
	int medium = 0;
	for (int begin = 0; begin < length; begin++)
	{
		for (int end = 0; end < length; end++)
		{
			printf("\n%c", G.vertex[begin]);
			medium = P[begin][end];                     //开始追溯(此为最近的前驱)
			while (medium != end)						//未追溯到尾
			{
				printf("->%c", G.vertex[medium]);		//打印中间结点
				medium = P[medium][end];				//向后追溯
			}
		}
	}
}

4、代码

//弗洛伊德(Floyd)算法
/*测试案例
ABCDEFGHI
B 1 C 5
A 1 C 3 D 7 E 5
A 5 B 3 E 1 F 7
B 7 E 2 G 3
B 5 C 1 F 3 H 9 G 6 D 2
C 7 E 3 H 5
D 3 E 6 H 2 I 7
F 5 E 9 G 2 I 4
G 7 H 4
*/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

#define MAXSIZE 20
#define MAX 65535							//代表无穷大
int length = 0;									//顶点个数
int D[MAXSIZE][MAXSIZE];		//存放顶点之间的权
int P[MAXSIZE][MAXSIZE];		//存放顶点之间的前驱(中间结点)

//图(顶点和权)
typedef struct
{
	char vertex[MAXSIZE];
	int weight[MAXSIZE][MAXSIZE];			//权可以代替边(自身为0,相连有值,不相连无穷大)
}Graph;
Graph G;


//输入顶点
void InputVertex()
{
	int i;
	char ch;
	printf("请输入图的顶点:\n");
	scanf("%c", &ch);
	for (i = 0; i < MAXSIZE && ch != '\n'; i++)
	{
		G.vertex[i] = ch;
		scanf("%c", &ch);
	}
	length = i;
}

//图权重初始化
void GraphWeightInit()
{
	int i, j;
	for (i = 0; i < length; i++)
	{
		for (j = 0; j < length; j++)
		{
			if (i == j)							//指向自己
				G.weight[i][j] = 0;
			else
				G.weight[i][j] = MAX;	//无穷大
		}
	}
}

//根据数据查找图顶点下标
int FindIndex(char ch)
{
	int i;
	for (i = 0; i < length; i++)
	{
		if (G.vertex[i] == ch)
			return i;
	}
	return -1;
}

//创建图
void CreateGraph()
{
	int i, j, index, weight;
	char ch;
	for (i = 0; i < length; i++)
	{
		printf("请输入%c的邻接顶点及权重(空格分隔,换行结束):\n", G.vertex[i]);
		scanf("%c", &ch);
		while (ch != '\n')
		{
			while (ch == ' ')				//为空格
			{
				scanf("%c", &ch);			//输入字符
				continue;
			}
			index = FindIndex(ch);
			scanf("%d", &weight);		//输入权重
			while (weight == 32)		//32为空格的ASCII码
			{
				scanf("%d", &weight);
				continue;
			}
			G.weight[i][index] = weight;	//存入权重
			scanf("%c", &ch);				//(下一轮)输入字符
		}
	}
}

//弗洛伊德算法
void Floyd()
{
	int medium, begin, end;
	//初始化矩阵
	for (int i = 0; i < length; i++)
		for (int j = 0; j < length; j++)
		{
			D[i][j] = G.weight[i][j];
			P[i][j] = j;
		}

	//开始正式修改(最短路径及前驱)
	for (medium = 0; medium < length; medium++)	//中间结点
		for (begin = 0; begin < length; begin++)			//前驱结点
			for (end = 0; end < length; end++)				//后继结点
			{
				//经过中间结点路径更小,则1、需要覆盖掉原来的路径;2、替换掉前驱(中间结点)
				if (D[begin][end] > (D[begin][medium] + D[medium][end]))
				{
					D[begin][end] = D[begin][medium] + D[medium][end];		//覆盖路径(只达标的话,只要这一句就够了)
					P[begin][end] = P[begin][medium];										//更新前驱(中间结点)
					//不能直接赋值medium:跨越结点之间的追溯,存放的是最近前驱,需要一个一个往后追溯
				}
			}
}

//测试矩阵输出
void PrintArray()
{
	//遍历输出
	printf("遍历输出D矩阵(最短路径):\n");
	for (int i = 0; i < length; i++)
	{
		printf("\n");
		for (int j = 0; j < length; j++)
		{
			printf("%3d", D[i][j]);
		}
	}
	printf("\n遍历输出P矩阵(前驱):\n");
	for (int i = 0; i < length; i++)
	{
		printf("\n");
		for (int j = 0; j < length; j++)
		{
			printf("%3d", P[i][j]);
		}
	}
}

//遍历弗洛伊德算法
//确定begin -> end:从最近的前驱开始,一点一点往后追溯
void Traverse_Floyd()
{
	int medium = 0;
	for (int begin = 0; begin < length; begin++)
	{
		for (int end = 0; end < length; end++)
		{
			printf("\n%c", G.vertex[begin]);
			medium = P[begin][end];						//开始追溯(此为最近的前驱)
			while (medium != end)							//未追溯到尾
			{
				printf("->%c", G.vertex[medium]);		//打印中间结点
				medium = P[medium][end];				//向后追溯
			}
		}
	}
}

//输出测试
void Print()
{
	for (int i = 0; i < length; i++)
	{
		printf("\n%c结点邻接结点:\t", G.vertex[i]);
		for (int j = 0; j < length; j++)
		{
			if (G.weight[i][j] != 0 && G.weight[i][j] != MAX)		//有邻接结点
			{
				printf("%c %d\t", G.vertex[j], G.weight[i][j]);
			}
		}
	}
}

int main()
{
	InputVertex();			//输入顶点

	GraphWeightInit();		//图权重初始化

	CreateGraph();			//创建图

	Floyd();				//弗洛伊德算法(生成最短路径)
	Traverse_Floyd();		//遍历弗洛伊德算法
	//PrintArray();			//测试弗洛伊德矩阵输出
	//Print();				//测试输出

	return 0;
}



参考资料

《大话数据结构》 

https://www.bilibili.com/video/BV1uX4y137Hf?from=search&seid=9442880507495572891

https://blog.csdn.net/jeffleo/article/details/53349825?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162842804216780271587280%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162842804216780271587280&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-53349825.pc_search_result_control_group&utm_term=%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

https://blog.csdn.net/yuewenyao/article/details/81021319?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162842804216780271587280%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162842804216780271587280&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-81021319.pc_search_result_control_group&utm_term=%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

https://zhuanlan.zhihu.com/p/33162490 

上一篇:实验报告(Dijkstra算法 )


下一篇:各种搜索汇总