《数据结构（C语言版）第二版》第六章-图（6.6 图的应用——6.6.2 最短路径）

6.6.2.1 从某个源点到其余各顶点的最短路径

迪杰斯特拉算法

C语言常见问题——数组初始化的四种方法 —— 易水卷长空

#include <stdio.h>
#include <stdlib.h>

#define MaxInt 32767
#define MVNum 100

typedef char VerTexType;
typedef int ArcType;


bool S[MVNum]; //记录从源点v0到终点vi是否已被确定最短路径长度，true表示确定，false表示尚未确定。
ArcType D[MVNum]; //记录从源点v0到终点vi的当前最短路径长度。
int Path[MVNum]; //记录从源点v0到终点vi的当前最短路径上vi的直接前驱顶点序号（下标）。
//这三个数组中的每个下标，与G.vexs中各顶点的下标是一致的

int reverse[MVNum];  //未对reverse数组进行初始化时，需将其定义为全局变量

typedef struct
{
	VerTexType vexs[MVNum];
	ArcType arcs[MVNum][MVNum];
	int vexnum;
	int arcnum;
}AMGraph;

void CreateAMGraph(AMGraph& G);
int LocateVex(AMGraph G, VerTexType v);
void printAMGraph(AMGraph G);
void ShortestPath(AMGraph G, int v0);
void printPath(AMGraph G, int v0);

int main()
{
	AMGraph G = { {0},{0},0,0 };
	int i = 0;
	CreateAMGraph(G);
	printAMGraph(G);

	printf("\n");
	ShortestPath(G, 0);
	printPath(G, 0);

	return 0;
}


//创建带权有向网的邻接矩阵
void CreateAMGraph(AMGraph& G)
{
	int i = 0;
	int j = 0;
	int k = 0;
	VerTexType v1 = '\0';
	VerTexType v2 = '\0';
	ArcType w = 0;

	printf("请输入总顶点数：");
	scanf_s(" %d", &G.vexnum);

	printf("请输入总边数：");
	scanf_s(" %d", &G.arcnum);

	for (i = 0; i < G.vexnum; i++)
	{
		printf("请输入第%d个顶点的值：", i + 1);
		scanf_s(" %c", &G.vexs[i]);

		for (j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j] = MaxInt;
		}
	}

	for (k = 0; k < G.arcnum; k++)
	{
		printf("请输入第%d条边的两个顶点：", k + 1);
		scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));

		printf("请输入第%d条边的权值：", k + 1);
		scanf_s(" %d", &w);

		i = LocateVex(G, v1);
		j = LocateVex(G, v2);

		G.arcs[i][j] = w;
	}
}

int LocateVex(AMGraph G, VerTexType v)
{
	int i = 0;

	for (i = 0; i < G.vexnum && (G.vexs[i] != v); i++)
	{
		;
	}

	return i;
}

void printAMGraph(AMGraph G)
{
	int i = 0;
	int j = 0;

	printf("各顶点值为：");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%c ", G.vexs[i]);
	}

	printf("\n邻接矩阵为：\n");
	for (i = 0; i < G.vexnum; i++)
	{
		for (j = 0; j < G.vexnum; j++)
		{
			if (G.arcs[i][j] == MaxInt)
			{
				printf("%d   ", G.arcs[i][j]);
			}
			else if (G.arcs[i][j] > 9)
			{
				printf("%d      ", G.arcs[i][j]);
			}
			else
			{
				printf("%d       ", G.arcs[i][j]);
			}
		}

		printf("\n");
	}
}

//用Dijkstra算法求有向网G的下标为vO的顶点到其余顶点的最短路径
void ShortestPath(AMGraph G, int v0)
{
	int n = G.vexnum;
	int v = 0;
	int i = 0;
	int min = 0;
	int w = 0;

	for (v = 0; v < n; ++v)
	{
		if (v != v0)
		{
			S[v] = false;
			D[v] = G.arcs[v0][v];

			if (D[v] < MaxInt)
			{
				Path[v] = v0;
			}
			else
			{
				Path[v] = -1;
			}
		}
		else
		{
			S[v] = true;
			D[v] = 0;
			Path[v] = -1;
		}
	}

	for (i = 1; i < n; i++)
	{
		//在未被确定最短路径长度的顶点中(S[w]为false）,寻找各顶点最短路径长度D[w]的最小值min
		min = MaxInt;
		for (w = 0; w < n; ++w)
		{
			if (!S[w] && D[w] < min)
			{
				v = w;
				min = D[w];
			}
		}

		S[v] = true;

		for (w = 0; w < n && v < n; ++w)  //这里必须限制v < n，因为当以G.vexs中最后一个顶点为源点时，v会在自增后跳出初始化的for循环，即会等于G.vexnum
		{
			if (!S[w] && (D[v] + G.arcs[v][w] < D[w]))
			{
				D[w] = D[v] + G.arcs[v][w];
				Path[w] = v;
			}
		}
	}

	/* 在最后的for循环if条件中,一定不要加D[v]!=MaxInt这个条件，因为当从下标为v0的源点到下标为w的顶点之间不存在弧时，D[w]的值为MaxInt.
  此时以下标为v的顶点为中转点的路径(Vv0,Vv,Vw)就是从下标为v0的源点到下标为w的顶点之间的最短路径，需要对D[w]及Path[w]的值都进行更新。
  而且此if中加上条件 G.arcs[v][w] != MaxInt 也不会起作用，因为当G.arcs[v][w]为MaxInt时，D[w]的最大值为MaxInt，
  而D[v]也一定为非负值，因此后面的 D[v] + G.arcs[v][w] < D[w] 一定不会成立。  */

	printf("\n\n打印S数组：");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%d ", S[i]);
	}

	printf("\n打印D数组：");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%d ", D[i]);
	}

	printf("\n打印Path数组：");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%d ", Path[i]);
	}
}


//最好用栈或递归
void printPath(AMGraph G, int v0)
{
	int i = 0;
	int j = 0;
	int k = 0;
	//int reverse[MVNum] = {0}; 或者把reverse数组定义为全局变量，或者如此对reverse数组进行初始化（不同于数组作为函数形参，当不列出数组中的所有元素时，必须要指明数组大小）
	//如果初始化列表包含数组a的所有元素，才可以省略数组的长度

	for (i = 0; i < G.vexnum; i++)
	{
		if (i != v0)
		{
			if (Path[i] == -1)
			{
				printf("\n以第%d个顶点%c为源点，到终点%c无最短路径。", v0 + 1, G.vexs[v0], G.vexs[i]);
			}
			else
			{
				reverse[0] = i;
				for (j = 1, k = Path[i]; j < G.vexnum && k != v0; j++, k = Path[k])
				{
					reverse[j] = k;
				}
				reverse[j] = v0;

				printf("\n以第%d个顶点%c为源点，到终点%c的最短路径为：", v0 + 1, G.vexs[v0], G.vexs[i]);
				for (k = j; k >= 0; k--)
				{
					if (k > 0)
					{
						printf("%c -> ", G.vexs[reverse[k]]);
					}
					else
					{
						printf("%c ", G.vexs[reverse[k]]);
					}
				}
				printf("，权值为：%d", D[i]);
			}
		}
	}
}

使用递归输出到其余各顶点的最短路径

//使用递归输出到其余各顶点的最短路径
void find(AMGraph G, int v0, int i)
{
	//printf("\nv0 = %d , i = %d\n", v0, i);
	if (i == v0)
	{
		printf("%c", G.vexs[v0]); // 到达源点，直接输出 
		return;
	}
	else
	{
		//printf("\nv0 = %d , Path[i] = Path[%d] = %d\n",v0,i, Path[i]);
		find(G, v0, Path[i]); // 递归地打印前驱顶点，v0 = 0, i = 3，Path[3] = 4，Path[4] = 0
		//printf("\nG.vexs[i] =  G.vexs[%d] = %c\n", i, G.vexs[i]);
		printf(" -> %c", G.vexs[i]); // 打印当前顶点
	}
}

void printPath(AMGraph G, int v0)
{
	int i = 0;

	for (i = 0; i < G.vexnum; i++)
	{
		if (i != v0)
		{
			if (Path[i] == -1)
			{
				printf("\n以第%d个顶点%c为源点，到终点%c无最短路径。", v0 + 1, G.vexs[v0], G.vexs[i]);
			}
			else
			{
				printf("\n以第%d个顶点%c为源点，到终点%c的最短路径为：", v0 + 1, G.vexs[v0], G.vexs[i]);
				find(G, v0, i);  //v0 = 0, i = 3
				printf("，权值为：%d", D[i]);
			}
		}
	}
}

6.6.2.2 每一对顶点之间的最短路径

6.6.2.2.1 调用n次迪杰斯特拉算法

#include <stdio.h>
#include <stdlib.h>

#define MaxInt 32767
#define MVNum 100

typedef char VerTexType;
typedef int ArcType;


bool S[MVNum]; //记录从源点v0到终点vi是否已被确定最短路径长度，true表示确定，false表示尚未确定。
ArcType D[MVNum]; //记录从源点v0到终点vi的当前最短路径长度。
int Path[MVNum]; //记录从源点v0到终点vi的当前最短路径上vi的直接前驱顶点序号（下标）。
//这三个数组中的每个下标，与G.vexs中各顶点的下标是一致的

int reverse[MVNum];  //未对reverse数组进行初始化时，需将其定义为全局变量

typedef struct
{
	VerTexType vexs[MVNum];
	ArcType arcs[MVNum][MVNum];
	int vexnum;
	int arcnum;
}AMGraph;

void CreateAMGraph(AMGraph& G);
int LocateVex(AMGraph G, VerTexType v);
void printAMGraph(AMGraph G);
void ShortestPath(AMGraph G, int v0);
void printPath(AMGraph G, int v0);

int main()
{
	AMGraph G = { {0},{0},0,0 };
	int i = 0;
	CreateAMGraph(G);
	printAMGraph(G);

	for (i = 0; i < G.vexnum; i++)
	{
		printf("\n");
		ShortestPath(G, i);
		printPath(G, i);
	}

	return 0;
}


//创建带权有向网的邻接矩阵
void CreateAMGraph(AMGraph& G)
{
	int i = 0;
	int j = 0;
	int k = 0;
	VerTexType v1 = '\0';
	VerTexType v2 = '\0';
	ArcType w = 0;

	printf("请输入总顶点数：");
	scanf_s(" %d", &G.vexnum);

	printf("请输入总边数：");
	scanf_s(" %d", &G.arcnum);

	for (i = 0; i < G.vexnum; i++)
	{
		printf("请输入第%d个顶点的值：", i + 1);
		scanf_s(" %c", &G.vexs[i]);

		for (j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j] = MaxInt;
		}
	}

	for (k = 0; k < G.arcnum; k++)
	{
		printf("请输入第%d条边的两个顶点：", k + 1);
		scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));

		printf("请输入第%d条边的权值：", k + 1);
		scanf_s(" %d", &w);

		i = LocateVex(G, v1);
		j = LocateVex(G, v2);

		G.arcs[i][j] = w;
	}
}

int LocateVex(AMGraph G, VerTexType v)
{
	int i = 0;

	for (i = 0; i < G.vexnum && (G.vexs[i] != v); i++)
	{
		;
	}

	return i;
}

void printAMGraph(AMGraph G)
{
	int i = 0;
	int j = 0;

	printf("各顶点值为：");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%c ", G.vexs[i]);
	}

	printf("\n邻接矩阵为：\n");
	for (i = 0; i < G.vexnum; i++)
	{
		for (j = 0; j < G.vexnum; j++)
		{
			if (G.arcs[i][j] == MaxInt)
			{
				printf("%d   ", G.arcs[i][j]);
			}
			else if(G.arcs[i][j] > 9)
			{
				printf("%d      ", G.arcs[i][j]);
			}
			else
			{
				printf("%d       ", G.arcs[i][j]);
			}
		}

		printf("\n");
	}
}

//用Dijkstra算法求有向网G的下标为vO的顶点到其余顶点的最短路径
void ShortestPath(AMGraph G, int v0)
{
	int n = G.vexnum;
	int v = 0;
	int i = 0;
	int min = 0;
	int w = 0;

	for (v = 0; v < n; ++v)
	{
		if (v != v0)
		{
			S[v] = false;
			D[v] = G.arcs[v0][v];

			if (D[v] < MaxInt)
			{
				Path[v] = v0;
			}
			else
			{
				Path[v] = -1;
			}
		}
		else
		{
			S[v] = true;
			D[v] = 0;
			Path[v] = -1;
		}
	}

	for (i = 1; i < n; i++)
	{
		//在未被确定最短路径长度的顶点中(S[w]为false）,寻找各顶点最短路径长度D[w]的最小值min
		min = MaxInt;
		for (w = 0; w < n; ++w)
		{
			if (!S[w] && D[w] < min)
			{
				v = w;
				min = D[w];
			}
		}

		S[v] = true;

		for (w = 0; w < n && v < n; ++w)  //这里必须限制v < n，因为当以G.vexs中最后一个顶点为源点时，v会在自增后跳出初始化的for循环，即会等于G.vexnum
		{
			if (!S[w] && (D[v] + G.arcs[v][w] < D[w]))
			{
				D[w] = D[v] + G.arcs[v][w];
				Path[w] = v;
			}
		}
	}

		/* 在最后的for循环if条件中,一定不要加D[v]!=MaxInt这个条件，因为当从下标为v0的源点到下标为w的顶点之间不存在弧时，D[w]的值为MaxInt.
	  此时以下标为v的顶点为中转点的路径(Vv0,Vv,Vw)就是从下标为v0的源点到下标为w的顶点之间的最短路径，需要对D[w]及Path[w]的值都进行更新。
	  而且此if中加上条件 G.arcs[v][w] != MaxInt 也不会起作用，因为当G.arcs[v][w]为MaxInt时，D[w]的最大值为MaxInt，
	  而D[v]也一定为非负值，因此后面的 D[v] + G.arcs[v][w] < D[w] 一定不会成立。  */

	printf("\n\n打印S数组：");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%d ", S[i]);
	}

	printf("\n打印D数组：");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%d ", D[i]);
	}

	printf("\n打印Path数组：");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%d ", Path[i]);
	}
}


//最好用栈或递归
void printPath(AMGraph G, int v0)
{
	int i = 0;
	int j = 0;
	int k = 0;
	//int reverse[MVNum] = {0}; 或者把reverse数组定义为全局变量，或者如此对reverse数组进行初始化（不同于数组作为函数形参，当不列出数组中的所有元素时，必须要指明数组大小）
	//如果初始化列表包含数组a的所有元素，才可以省略数组的长度

	for (i = 0; i < G.vexnum; i++)
	{
		if (i != v0)
		{
			if (Path[i] == -1)
			{
				printf("\n以第%d个顶点%c为源点，到终点%c无最短路径。", v0 + 1, G.vexs[v0], G.vexs[i]);
			}
			else 
			{
				reverse[0] = i;
				for (j = 1, k = Path[i];j <G.vexnum && k != v0; j++, k = Path[k])
				{					
					reverse[j] = k;
				}
				reverse[j] = v0;

				printf("\n以第%d个顶点%c为源点，到终点%c的最短路径为：", v0 + 1, G.vexs[v0], G.vexs[i]);
				for (k = j; k >= 0; k--)
				{
					if (k > 0)
					{
						printf("%c -> ", G.vexs[reverse[k]]);
					}
					else
					{
						printf("%c ", G.vexs[reverse[k]]);
					}
				}
				printf("，权值为：%d", D[i]);
			}
		}
	}
}

6.6.2.2.2 弗洛伊德算法

#include <stdio.h>
#include <stdlib.h>

#define MaxInt 32767
#define MVNum 100

typedef char VerTexType;
typedef int ArcType;

ArcType D[MVNum][MVNum]; //记录顶点Vi和Vj之间的最短路径长度。
int Path[MVNum][MVNum]; //最短路径上顶点Vj的前一顶点的序号（下标）。
//这两个数组中的关于顶点的每个下标，与G.vexs中各顶点的下标是一致的

typedef struct
{
	VerTexType vexs[MVNum];
	ArcType arcs[MVNum][MVNum];
	int vexnum;
	int arcnum;
}AMGraph;

void CreateAMGraph(AMGraph& G);
int LocateVex(AMGraph G, VerTexType v);
void printAMGraph(AMGraph G);
void ShortestPath_Floyd(AMGraph G);
void find(AMGraph G, int i, int j);
void printPath(AMGraph G);


int main()
{
	AMGraph G = { {0},{0},0,0 };
	int i = 0;
	CreateAMGraph(G);
	printAMGraph(G);

	printf("\n");
	ShortestPath_Floyd(G);
	printPath(G);

	return 0;
}


//创建带权有向网的邻接矩阵
void CreateAMGraph(AMGraph& G)
{
	int i = 0;
	int j = 0;
	int k = 0;
	VerTexType v1 = '\0';
	VerTexType v2 = '\0';
	ArcType w = 0;

	printf("请输入总顶点数：");
	scanf_s(" %d", &G.vexnum);

	printf("请输入总边数：");
	scanf_s(" %d", &G.arcnum);

	for (i = 0; i < G.vexnum; i++)
	{
		printf("请输入第%d个顶点的值：", i + 1);
		scanf_s(" %c", &G.vexs[i]);

		for (j = 0; j < G.vexnum; j++)
		{
			if (i != j)
			{
				G.arcs[i][j] = MaxInt;
			}
			else
			{
				G.arcs[i][j] = 0;  
				/* 在弗洛伊德算法中，每个顶点到其自身，（中间不存在弧），就已经是最短路径了。
				即使可以通过其它顶点中转再到达其本身，也是比其直接到其自身长的，
				所以把每个顶点与自身之间的权值均设为0.  */
			}
		}
	}

	for (k = 0; k < G.arcnum; k++)
	{
		printf("请输入第%d条边的两个顶点：", k + 1);
		scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));

		printf("请输入第%d条边的权值：", k + 1);
		scanf_s(" %d", &w);

		i = LocateVex(G, v1);
		j = LocateVex(G, v2);

		G.arcs[i][j] = w;
	}
}

int LocateVex(AMGraph G, VerTexType v)
{
	int i = 0;

	for (i = 0; i < G.vexnum && (G.vexs[i] != v); i++)
	{
		;
	}

	return i;
}

void printAMGraph(AMGraph G)
{
	int i = 0;
	int j = 0;

	printf("各顶点值为：");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%c ", G.vexs[i]);
	}

	printf("\n邻接矩阵为：\n");
	for (i = 0; i < G.vexnum; i++)
	{
		for (j = 0; j < G.vexnum; j++)
		{
			if (G.arcs[i][j] == MaxInt)
			{
				printf("%d   ", G.arcs[i][j]);
			}
			else if (G.arcs[i][j] > 9)
			{
				printf("%d      ", G.arcs[i][j]);
			}
			else
			{
				printf("%d       ", G.arcs[i][j]);
			}
		}

		printf("\n");
	}
}

//用Floyd算法求有向网G中各对顶点i和j之间的最短路径
void ShortestPath_Floyd(AMGraph G)
{
	int i = 0;
	int j = 0;
	int k = 0;

	for (i = 0; i < G.vexnum; i++)
	{
		for (j = 0; j < G.vexnum; j++)
		{
			D[i][j] = G.arcs[i][j];

			if (D[i][j] < MaxInt && D[i][j] != 0  )
			{
				Path[i][j] = i;
			}
			else
			{
				Path[i][j] = -1;
			}
		}
	}

	for (k = 0; k < G.vexnum; k++)
	{
		for (i = 0; i < G.vexnum; i++)
		{
			for (j = 0; j < G.vexnum; j++)
			{
				if (D[i][k] + D[k][j] < D[i][j])
				{
					D[i][j] = D[i][k] + D[k][j];
					Path[i][j] = Path[k][j];
				}
			}
		}
	}
}

//递归打印G中从下标为i的顶点，到下标为j的顶点的最短路径
void find(AMGraph G, int i, int	j)
{
	if (i == j)
	{
		printf("%c ", G.vexs[i]);
		return;
	}
	else
	{
		find(G, i, Path[i][j]);  //不断取从序号为i的顶点到序号为j的顶点最短路径上，序号为j的顶点的直接前驱顶点的序号
		printf(" -> %c", G.vexs[j]); //并且打印该序号对应的顶点值
	}
}

void printPath(AMGraph G)
{
	int i = 0;
	int j = 0;

	for (i = 0; i < G.vexnum; i++)
	{
		for (j = 0; j < G.vexnum; j++)
		{
			if (j != i)
			{
				if (Path[i][j] == -1)
				{
					printf("\n从第%d个顶点%c到第%d个顶点%c不存在最短路径。", i + 1, G.vexs[i], j + 1, G.vexs[j]);
				}
				else
				{
					printf("\n从第%d个顶点%c到第%d个顶点%c的最短路径为：", i + 1, G.vexs[i], j + 1, G.vexs[j]);
					find(G, i, j);
					printf(" ，其长度为：%d", D[i][j]);
				}
			}
		}
	}
}

上例中带权有向网的输出结果（两种算法输出一致。）

使用递归读取两个顶点之间的最短路径

//递归打印G中从下标为i的顶点，到下标为j的顶点的最短路径
void find(AMGraph G, int i, int	j)
{
	printf("\ni = %d , j = %d\n\n",i,j);

	if (i == j)
	{
		printf("%c ", G.vexs[i]);
		return;
	}
	else
	{
		printf("\ni = %d , Path[i][j] = Path[%d][%d] = %d\n\n",i, i,j,Path[i][j]);
		find(G, i, Path[i][j]);  //不断取从序号为i的顶点到序号为j的顶点最短路径上，序号为j的顶点的直接前驱顶点的序号

		printf("\n\nG.vexs[i] =  G.vexs[%d] = %c", i, G.vexs[i]);
		printf("\nG.vexs[j] =  G.vexs[%d] = %c", j, G.vexs[j]);
		printf("\nG.vexs[Path[i][j]] = G.vexs[Path[%d][%d]] = G.vexs[%d] = %c\n\n",i,j,Path[i][j], G.vexs[Path[i][j]]);
		printf(" -> %c", G.vexs[j]); //并且打印该序号对应的顶点值
	}
}