数据结构方法(一)：图之单源最短路径

单源最短路径

百度百科

给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径 [1] 问题。

问题描述

给定一个带权有向图 G=(V,E)。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

Dijkstra算法的解决方案

即先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

Dijkstra算法的解题思想

• 选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径

  • 创建一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行
  • 设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。

• 在上述的最短路径dist[]中选一条最短的，并将其终点（即）k加入到集合s中。

• 调整T中各顶点到源点v的最短路径。 因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。

  • 调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。即算法当中的

    if(min + g.edges[v][k] < d[k])
    {
        d[k] = min + g.edges[v][k];
    }

• 再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。

举个书上的题当作例子

初始化的距离向量

• 选A作为源点，A到各顶点的距离即为距离向量

			A	B	C	D	E	F	G
循环	集合S	v	0	1	2	3	4	5	6
初始化	{A}	-	0	48	∞	15	28	∞	40

这时候的路径向量为：

• 只有与A有点关联的结点才有路径向量为0,其他均为 -1

			A	B	C	D	E	F	G
循环	集合S	v	0	1	2	3	4	5	6
初始化	{A}	-	-1	0	-1	0	0	-1	0

---

接下来，就是将源点A到其他结点距离最短的结点找出来，这里最短的是到D结点加到集合S当中,并且：

• 由于D的加入，导致A到F的距离由∞变为33 + 15 = 48
• A到G的距由40变为A->D->G = 15 + 23 = 38
• D的下标为3,所以v变为3

距离向量变为：

			A	B	C	D	E	F	G
循环	集合S	v	0	1	2	3	4	5	6
初始化	{A}	-	0	48	∞	15	28	∞	40
1	{A,D}	3	0	48	∞	15	28	48	38

由于现在A到G和F通过了D顶点，导致顶点G和F的前驱结点变为了D，即路径向量变为3

路径向量为：

			A	B	C	D	E	F	G
循环	集合S	v	0	1	2	3	4	5	6
初始化	{A}	-	-1	0	-1	0	0	-1	0
1	{A,D}	3	-1	0	-1	0	0	3	3

---

接下来继续向后找，发现最短的路径是到E,所以将其加入集合S，并且：

• A到C的距离由∞变为了A->E->C = 28 + 33 = 61
• 其他的均未变化

距离向量变为：

			A	B	C	D	E	F	G
循环	集合S	v	0	1	2	3	4	5	6
初始化	{A}	-	0	48	∞	15	28	∞	40
1	{A,D}	3	0	48	∞	15	28	48	38
2	{A,D,E}	4	0	48	61	15	28	48	38

由于A->C变成了A->E->C,所以C的前驱结点变为了E，即4

路径向量为：

			A	B	C	D	E	F	G
循环	集合S	v	0	1	2	3	4	5	6
初始化	{A}	-	-1	0	-1	0	0	-1	0
1	{A,D}	3	-1	0	-1	0	0	3	3
2	{A,D,E}	4	-1	0	4	0	0	3	3

---

继续向下推导，最终结果为：

距离向量：

			A	B	C	D	E	F	G
循环	集合S	v	0	1	2	3	4	5	6
初始化	{A}	-	0	48	∞	15	28	∞	40
1	{A,D}	3	0	48	∞	15	28	48	38
2	{A,D,E}	4	0	48	61	15	28	48	38
3	{A,D,E,G}	6	0	48	61	15	28	48	38
4	{A,D,E,G,B}	1	0	48	60	15	28	48	38
5	{A,D,E,G,B,F}	4	0	48	57	15	28	48	38
6	{A,D,E,G,B,F,C}	2	0	48	57	15	28	48	28

路径向量：

			A	B	C	D	E	F	G
循环	集合S	v	0	1	2	3	4	5	6
初始化	{A}	-	-1	0	-1	0	0	-1	0
1	{A,D}	3	-1	0	-1	0	0	3	3
2	{A,D,E}	4	-1	0	4	0	0	3	3
3	{A,D,E,G}	6	-1	0	4	0	0	3	3
4	{A,D,E,G,B}	1	-1	0	1	0	0	3	3
5	{A,D,E,G,B,F}	4	-1	0	5	0	0	3	3
6	{A,D,E,G,B,F,C}	2	-1	0	5	0	0	3	3

可以从表中的数据得出：

• 由于B的路径向量为0,即A,所以A->B的最短路径就是A->B
• C的路径向量为5，即F,而F的路径向量为3，即D,D的路径向量为0,是A,所以A到C的最短路径即为 A->D->F->C

总结为：

首尾	最短长度	最短路径
A->B	48	A->B
A->C	57	A->D->F->C
A->D	15	A->D
A->E	28	A->E
A->F	48	A->D->F
A->G	28	A->D->G

代码：

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define M 30  /*预定义图的最大顶点数*/
#define FINITY 5000  //用 5000代替无穷


//最小生成树算法的结构体
typedef struct {
	char vexs[M];  //顶点的数据域
	int edges[M][M];  //定义的邻接矩阵
	int n, e;  //图中的顶点数和边数
}Mgraph;


typedef struct edgedata
{
	int beg, en;  //beg,en都是顶点序号
	int length;  //边长
}edge;



void create(Mgraph *g, char *filename, int c)  //c = 0表示创建无向图 
{
	int weight = 0;  //边的权值
	int front, rear; //变得前驱和后驱
	FILE *file;
	file = fopen(filename, "r"); //从文件读取图的边信息
	if (file)
	{
		fscanf(file, "%d%d\n", &g->n, &g->e);  //读取图的顶点数与边数
		for (int i = 0; i < g->n; i++)
		{
			fscanf(file, "%c", &g->vexs[i]);  //读取图中顶点的信息域
		}
		for (int i = 0; i < g->n; i++)
		{
			for (int j = 0; j < g->n; j++)
			{
				if (i == j)
					g->edges[i][j] = 0;  //对角线上的均为0
				else
					g->edges[i][j] = FINITY;  //没有赋值的域均加成无
			}
		}
		for (int k = 0; k < g->e; k++)
		{
			fscanf(file, "%d%d%d", &front, &rear, &weight);
			g->edges[front][rear] = weight;  //只些相应顺序的，即有向图
			if (c == 0)
				g->edges[rear][front] = weight;  //对称图形，即为无向图
		}
		fclose(file);
	}
	else
	{
		g->n = 0;
		printf("文件打开失败！\n");
	}
}


// 图的最短路径
 typedef enum{FALSE,TRUE} boolean;  /*FALSE 为0，TRUE为1*/
 typedef int dist[M];  //距离向量类型
 typedef int path[M];  //路径类型

 /*
 Dijkstra算法求单源最短路径
 g 有向图
 root 根节点
 p 路径   p[i] 用于保存最短路径上第i个顶点的前驱顶点的序号
 d 距离向量  用于保存从源点出发的顶点到其他顶点的距离向量
 */
 void Dijkstra(Mgraph g,int root,path p, dist d)
 {
	 int v = 0;  //用于临时保存
	 int min = 0;
	 boolean final[M];  //表示当前元素是否已经求出最短路径，定义为布尔类型
	 for (int i = 0; i < g.n; i++)  //初始化各种集合与距离向量
	 {
		 final[i] = FALSE;  //全部赋值为FALSE
		 d[i] = g.edges[root][i];
		 if (d[i] < FINITY && d[i] != 0)  //非自我路径和达不到的路径  
			 p[i] = root;  //前驱结点为根结点
		 else
			 p[i] = -1;  //当前结点无前驱结点
	 }
	 final[root] = TRUE; //初始时s只有一个根节点root一个结点
	 d[root] = 0;
	 printf("%d到其他顶点的最短距离为：\n", root);
	 for (int i = 1; i < g.n; i++)
	 {
		  min = FINITY;
		  for (int k = 0; k < g.n; ++k)  //循环找出最小边入结点
		  {
			  if (!final[k] && d[k] < min)  //如果还没有求出最短路径并且存在更短的路径
			  {
				  v = k;  //将初始结点替换为当前结点
				  min = d[k]; //min保存最短路径
			  }
		  }
		  
		  printf("\n%d-->%d 路径长度： %d\n",root,g.vexs[v], min);
		  if (min == FINITY)  //如果得出的路径无法达到
		  	  return;
		  final[v] = TRUE; //该结点已经求出最短路径
		  //修改S到V-S中各结点的距离
		  for (int i = 0; i < g.n; ++i)
			 if (!final[i] && (min + g.edges[v][i] < d[i]))
			 {
				  d[i] = min + g.edges[v][i]; //最短路径等于之前的最短路径加上最近的最短路径
				  p[i] = v;  //将 路径向量赋值
			 }
	 }
 }

 void print_dpd(Mgraph g, path p, dist d)
 {
	 int st[M], pre, top = -1;//定义栈st并初始化空栈
	 printf("\n\n最短路径为：\n\n");
	 for (int  i = 0; i < g.n; i++)
	 {
		 printf("路径长度：%3d  ", d[i]); //将距离向量输出
		 st[++top] = i; //将i入栈
		 pre = p[i];  //储存当前
		 while (pre != -1)
		 {
			 st[++top] = pre;  //让pre入栈
			 pre = p[pre];
		 }
		 printf("路径走向：");
		 while (top > 0)
			 printf("%2d", st[top--]);
		 printf("\n");
	 }
 }


int main()
{
	Mgraph g;
	char filename[20] = "D:\\Desktop\\Test.txt";
	path p; //路径向量
	dist d;  //最短路径向量
	int root;
	create(&g, filename, 1);
	printf("请输入源点：\n");
	scanf("%d", &root);
	Dijkstra(g, root, p, d);
	print_dpd(g, p, d);
	system("pause");
	return 0;
}

文件格式

输出结果：