一、问题描述
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<stdio.h>
#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 (n2)，采用邻接矩阵存储图，空间复杂度为O(n2)，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<stdio.h>
#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、代码运行效率分析文章来源：https://www.toymoban.com/news/detail-480791.html
Floyd算法是一种动态规划算法，运用三重循环暴力求解最短路径，该算法的时间复杂度为O（n3），运用了邻接矩阵存储图，空间复杂度为O (n2)为顶点数，相比于Dijsta算法，该算法简洁明了，易于实现，Floyd算法可以计算出图中任意两个顶点之间的最短距离，适用于计算多源最短路径，而 Floyd算法适用于计算单源最短路径。文章来源地址https://www.toymoban.com/news/detail-480791.html
到了这里，关于C语言数据结构——图的最短路径算法解决实例问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
