地铁建设问题

梗概

任务：某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。

​ ①从包含各辖区的地图文件读入辖区名称和各辖区间的直接距离；②根据读入的各辖区的距离信息，计算出应该建设哪些辖区间的地铁路线；③输出应该建设的地铁路线及所需建设的总里程信息。

思路概述

分析题目可知此题要求建设费用最小，究其本质是要我们抽象城市辖区为一个图的数据结构。并在这个图的结构上找出最小生成树。

​ 而最小生成树可以用克鲁斯卡尔算法(Kruskal),或是普里姆算法(Prim)进行求解。

克鲁斯卡尔算法与普里姆算法：
克鲁斯卡尔算法是一种使用贪婪方法的最小生成树算法。 该算法初始将图视为森林，图中的每一个顶点视为一棵单独的树。 一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性（不构成环）的树之间建立连边。

​ 普里姆算法则是选定初始点在已有节点的情况下选择最短的节点并更新已有节点路径，最后一步一步构建出最小生成树。

​ 算法讲解可以参考[这篇文章](图解：什么是最小生成树？ – 知乎 (zhihu.com))。
该文作者讲述详细精彩，当时给我一种醍醐灌顶的感觉。
本文用的是普里姆算法。为什么？因为我觉得这个比较简单😂。

完整代码

代码如下（示例）：

#include <stdio.h>

int map[9][9]={
        {   0,   3, 999, 999, 999,   4, 999, 999, 999},
        {   3,   0,   8, 999, 999, 999,   6, 999,   5},
        { 999,   8,   0,  12, 999, 999, 999, 999,   2},
        { 999, 999,  12,   0,  10, 999,  14,  16,  11},
        { 999, 999, 999,  10,   0,  18, 999,   1, 999},
        {   4, 999, 999, 999,  18,   0,   7, 999, 999},
        { 999,   6, 999,  14, 999,   7,   0,   9, 999},
        { 999, 999, 999,   6,   1, 999,   9,   0, 999},
        { 999,   5,   2,  11, 999, 999, 999, 999,   0}
};

int N = 9; ///城市个数

void print(int s[][9]);
int min(int s[][9], int *num);


void print(int s[][9])
{
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<9; j++)
        {
            printf("%4d", s[i][j]);
        }
        printf("\n");
    }
}
int min(int s[][9], int *num)
{
    int min = 999;
    int number;
    for(int i=0; i<9; i++)
    {
        if(s[0][i]<min && s[0][i] != 0)
        {
            min = s[0][i];
            number = i;
            *num = s[1][i];
        }
    }
    //printf("start = %d\n", num);
    //printf("end = %d\n", number);
    return number;
}


int main()
{
    int i, j, key, num;
    int s[2][9] = {};
    for(i=0; i<9; i++)
    {
        s[0][i] = map[0][i];
    }
    while(N>1)
    {
        N--;
        min(s, &num);
        printf("Start City:%d", num);
        printf("\tEnd City:%d\n", min(s, &num));
        key = min(s, &num);
        for(i=0; i<9; i++)
        {
            if(s[0][i] > map[key][i])
            {
                s[0][i] = map[key][i];
                s[1][i] = key;
            }
        }
        print(s);
    }
}

结果

注：结果中有两行数字，那是博主在调试代码时打印的数组，如有影响可以删去部分代码

总结

以上就是关于地铁问题博主发表的一点愚见，如若有更高明的建议，欢迎评论区留言！