C语言数据结构——图的最短路径算法解决实例问题

一、问题描述

W公司在某个地区有6个产品销售点，现根据业务需要打算在其中某个销售点上建立一个中心仓库，负责向其他销售点提供产品。由于运输线路不同，运输费用也不同。假定每天需要向每个销售点运输一次产品，那么应将中心仓库建在哪个销售点上，才能使运输费用达到最低。

二、算法实现

第一种算法——迪杰斯特拉算法实现

1、算法思路

迪杰斯特拉(Dijkstra)算法是典型最短路径算法， 是用于计算图中一个顶点到其他各顶点的最短路径，该算法的主要特点是以起始点为中心向外层层扩展(广度优先遍历思想)，直到扩展到终点为止。

（1）初始化一个起始顶点v0、数组Dist[maxsize]和Visited[maxsize]数组,Dist[maxsize]用于存储从该顶点到图中其他顶点的最短路径长度，Visited[maxsize]用于标记从vo结点到图中其他顶点是否已经找到了最短路径。

（2）算法首先让vo顶点到其所有邻接点的距离赋值给Dist数组，后选择与v0顶点相距最近的邻接点v1。继续从v1顶点出发，找到其所有邻接点，比较v0结点通过v1到v1的邻接点的路径距离是否变短，若变短，则将新的最短路径距离（v0到v1邻接点的距离）在Dist数组中进行更新。若v0到达一个顶点的最短距离已经求出，对其标志数组Visited赋值为1。

（3）重复（2）步骤，直到v0到所有图中顶点的最短路径距离求出，算法结束。

以上是实现迪杰斯特拉(Dijkstra)算法的实现，回到问题上，我们要将中心仓库建在一个销售点上，使得运输费用达到最低，为此们只需要在迪杰斯特拉(Dijkstra)算法外部加一个循环，依次计算图中的每一个销售点到其他销售点最小运输费用的总和。最终我们得出了使得运输费用达到最低的销售点，该销售点就是我们建中心仓库的最佳选择。

2、算法代码如下

#include
#define maxsize 10
#define inf 10000
typedef char VertexType;
typedef struct {
	VertexType vexs[maxsize];
	int arcs[maxsize][maxsize];
	int n, e;
} Mgraph;
//定位顶点v在顶点数组中的位置
int LocateVexPos(Mgraph* G, char v) {
	int i;
	for (i = 0; i < G->n; i++)
		if (G->vexs[i] == v)
			return i;
	return -1;
}
//根据构造无向图-邻接矩阵存储结构
void CreateMGraph(Mgraph* G)
{
	int i, j, k, posi, posj, temp;
	char vi, vj;
	printf("请输入图的顶点数和边数(输入格式为:顶点数,边数):  ");
	scanf_s("%d,%d", &(G->n), &(G->e));
	printf("请输入顶点信息(连续输入):  ");
	getchar();
	for (i = 0; i < G->n; i++)
		scanf_s("%c", &(G->vexs[i]), sizeof(char));
	for (i = 0; i < G->n; i++)
		for (j = 0; j < G->n; j++)
			G->arcs[i][j] = inf;
	getchar();
	for (k = 0; k < G->e; k++)
	{
		printf("请输入第%d条边(输入格式为:起点,终点,权值): ", k + 1);
		scanf_s("%c,%c,%d", &vi, sizeof(char), &vj, sizeof(char), &temp, sizeof(int));
		getchar();
		posi = LocateVexPos(G, vi);
		posj = LocateVexPos(G, vj);
		G->arcs[posi][posj] = temp;
		G->arcs[posj][posi] = temp;
	}
}
// 求一个顶点到其他顶点的最短路径—迪杰斯特拉算法（Dijsta）
int Dijsta_Path(Mgraph* G, int v0, int Dist[maxsize])
{
	int i, j, k, v, sum = 0;
	int visited[maxsize] = { 0 };
	for (i = 0; i < G->n; i++)
	{
		Dist[i] = G->arcs[v0][i];
	}
	visited[v0] = 1;
	Dist[v0] = 0;
	for (i = 1; i < G->n; i++)
	{
		int min = inf;
		for (j = 0; j < G->n; j++)
		{
			if (!visited[j])
			{
				if (Dist[j] < min)
				{
					v = j;
					min = Dist[j];
				}
			}
		}
		visited[v] = 1;
		for (k = 0; k < G->n; k++)
		{
			if (!visited[k] && (Dist[k] > min + G->arcs[v][k]))
			{
				Dist[k] = min + G->arcs[v][k];
			}
		}
	}
	for (i = 0; i < G->n; i++)
	{
		sum += Dist[i];
	}
	return sum;
}
void Calcu_Cost(Mgraph* G, int Dist[maxsize])
{
	int i, j, k, min_cost = inf;
	int cost[maxsize] = { 0 };
	for (i = 0; i < G->n; i++)
	{
		cost[i] = Dijsta_Path(G, i, Dist);
		if (cost[i] < min_cost)
		{
			min_cost = cost[i];
			k = i;
		}
	}
	printf("\n");
	for (i = 0; i < G->n; i++)
	{
		printf("中心仓库建在销售点%c上到其他销售点的总运输费用为：%d$\n", G->vexs[i], cost[i]);
	}
	printf("\n综上可知，中心仓库建在销售点%c时总运输费用最小，费用最小为：%d\n", G->vexs[k], min_cost);
}
void main()
{
	int Dist[maxsize];
	Mgraph G;
	CreateMGraph(&G);
	Calcu_Cost(&G, Dist);
}

3、代码运行结果：

4、代码运行效率分析

迪杰斯特拉 ( Dijkstra) 算法是 一个按路径长度递增的次序产生最短路径的算法，该算法是一种贪心算法，从代码实现上可以看出，运用两个循环结构进行求解，时间复杂度为 O (n^{2)，采用邻接矩阵存储图，空间复杂度为O(n}2)，n为图中顶点个数，当我们在解决运输费用达到最低这个问题时，需要计算图中的每一个销售点到其他销售点最小运输费用​的总和，因此需要原有算法的基础上再来一次循环，此时的时间复杂度为O (n^3)。

第二种算法—— 弗洛伊德（Floyd）算法实现

1、算法思路

弗洛伊德算法是一种用于求图中任意两顶点间最短路径的算法，该算法运用三重循环暴力求解，弗洛伊德算法中每一个顶点都是出发访问点，需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。该算法设定了两个二维数组，Path[maxsize][maxsize]和Dist[maxsize][maxszie],Path类似一个路径矩阵，记录一个顶点到图中其他顶点经过的路径顶点，Dist[maxsize][maxszie]类似一个最短距离矩阵，记录一个顶点到图中其他顶点的最短路径距离，弗洛伊德算法使用了三重循环，k为中转点，v为起点，w为终点，循环比较Dist[v][w] 和 Dist[v][k] + Dist[k][w] 最小值，如果Dist[v][k] + Dist[k][w] 为更小值，则把Dist[v][k] + Dist[k][w] 覆盖保存在Dist[v][w]中。
经过三重循环后，Dist数组中保存着每个顶点到图中其他顶点的最短距离。根据这个算法，我们计算图中每一个销售点到其他销售点最小运输费用的总和。最终我们可以得出使得运输费用达到最低的销售点，该销售点就是我们建中心仓库的最佳选择。

2、算法代码如下

#include
#define maxsize 10
#define inf 10000
typedef char VertexType;
typedef struct {
	VertexType vexs[maxsize];
	int arcs[maxsize][maxsize];
	int n, e;
}Mgraph;
//定位顶点v在顶点数组中的位置
int LocateVexPos(Mgraph* G, char v)
{
	int i;
	for (i = 0; i < G->n; i++)
		if (G->vexs[i] == v)
			return i;
	return -1;
}
//根据构造无向图-邻接矩阵存储结构
void CreateMGraph(Mgraph* G)
{
	int i, j, k, posi, posj, temp;
	char vi, vj;
	printf("请输入图的顶点数和边数(输入格式为:顶点数,边数):  ");
	scanf_s("%d,%d", &(G->n), &(G->e));
	printf("请输入顶点信息(连续输入):  ");
	getchar();
	for (i = 0; i < G->n; i++)
		scanf_s("%c", &(G->vexs[i]), sizeof(char));
	for (i = 0; i < G->n; i++)
	{
		for (j = 0; j < G->n; j++)
		{
			if (i == j)
				G->arcs[i][j] = 0;
			else
				G->arcs[i][j] = inf;
		}
	}
	getchar();
	for (k = 0; k < G->e; k++)
	{
		printf("请输入第%d条边(输入格式为:起点,终点,权值):  ", k + 1);
		scanf_s("%c,%c,%d", &vi, sizeof(char), &vj, sizeof(char), &temp, sizeof(int));
		getchar();
		posi = LocateVexPos(G, vi);
		posj = LocateVexPos(G, vj);
		G->arcs[posi][posj] = temp;
		G->arcs[posj][posi] = temp;
	}
}
// 求某个顶点到另一顶点的最短路径，弗洛伊德算法（Floyd算法）
void Floyd_path(Mgraph* G, int D[maxsize][maxsize])
{
	int v, w, u;
	for (v = 0; v < G->n; v++)
	{
		for (w = 0; w < G->n; w++)
		{
			D[v][w] = G->arcs[v][w];
		}
	}
	for (u = 0; u < G->n; u++)
	{
		for (v = 0; v < G->n; v++)
		{
			for (w = 0; w < G->n; w++)
			{
				if (D[v][w] > D[v][u] + D[u][w])
				{
					D[v][w] = D[v][u] + D[u][w];
				}
			}
		}
	}
}
void Calcul_Cost(Mgraph* G, int D[maxsize][maxsize])
{
	int i, j, k, min_cost = inf;
	int cost[maxsize] = { 0 };
	Floyd_path(G, D);
	for (i = 0; i < G->n; i++)
	{
		for (j = 0; j < G->n; j++)
		{
			cost[i] += D[i][j];
		}
		if (cost[i] < min_cost)
		{
			min_cost = cost[i];
			k = i;
		}
	}
	printf("\n");
	for (i = 0; i < G->n; i++)
	{
		printf("中心仓库建在销售点%c上到其他销售点的总运输费用为：%d$\n", G->vexs[i], cost[i]);
	}
	printf("\n综上可知，中心仓库建在销售点%c时总运输费用最小，费用最小为：%d\n", G->vexs[k], min_cost);
}
void main()
{
	int D[maxsize][maxsize];
	Mgraph G;
	CreateMGraph(&G);
	Calcul_Cost(&G, D);
}

3、代码运行结果 :

4、代码运行效率分析

Floyd算法是一种动态规划算法，运用三重循环暴力求解最短路径，该算法的时间复杂度为O（n3），运用了邻接矩阵存储图，空间复杂度为O (n2)为顶点数，相比于Dijsta算法，该算法简洁明了，易于实现，Floyd算法可以计算出图中任意两个顶点之间的最短距离，适用于计算多源最短路径，而 Floyd算法适用于计算单源最短路径。