接前一篇文章：软考 系统架构设计师系列知识点之杂项集萃（61）
第101题
下面的网络图表示从城市A到城市B运煤的各种路线。各线段上的数字表示该线段运煤所需的费用（百元/车）。城市A有3个装货点，城市B有3个卸货点，各点旁标注的数字表示装/卸煤所需的费用（百元/车）。根据该图，从城市A的一个装卸点经过一条路线到城市B的一个卸货点所需的装、运、卸总费用至少为（）（百元/车）。
A. 19
B. 20
C. 21
D. 22
正确答案：A。
所属知识点：旧版教材 数学与经济管理 -> 最短路径
解析：
解决这个问题，可以考虑从起点到终点层层推导的方式。具体过程如下图所示（其中红色字体标记的数字代表从起点到当前结点，最短路径长度）：
最短路径如下所示：
知识补强 —— Dijkstra算法
Dijkstra（迪杰斯特拉）算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
Dijkstra算法步骤
（1）初始化
1）选择一个源点（通常记为s）；
2）将所有顶点的最短路径长度初始化为无穷大（除了源点，其距离设为0）；
3）创建一个集合来存储已经找到最短路径的顶点（通常称为“已访问”集合）。
（2）选择未访问的顶点
从未访问的顶点中选择一个距离源点距离最小的顶点u。
（3）更新相邻顶点的距离
遍历顶点u的所有邻接点v。如果通过顶点u到顶点v的距离小于当前记录的距离，则更新顶点v的距离。
（4）标记顶点为已访问
将顶点u加入到已访问的集合中。
（5）重复以上过程
重复步骤（2）至（4），直到所有顶点都被访问过。
（6）结果
最终，所有顶点的最短路径长度将被计算出来。
本例中比单纯的Dijkstra算法复杂一些：原点不止1个而是3个；还要加上初始和结束权重。但是思想本身（意思）是一样的。
