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时总运输费用最小，费用最小为：%dn", 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#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时总运输费用最小，费用最小为：%dn", 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算法适用于计算单源最短路径。
