数据结构与算法：最短路径问题（1）

题目描述

摘自UNNC Programming and Algorithms (COMP1038) Coursework 2：

You are required to write a program that will produce the optimal route and cost C of train tickets between stations. To complete this task, you will be given a source station S, a destination station D and a distance matrix (in kilometers) for N stations. The cost C is defined as:

$$ C =⌈1.2 ∗ d+25∗n⌉ $$

where d is the total distance of the route, n is the number of intermediate stations (excluding source and destination stations), and $⌈x⌉$ means x should be rounded up to the next nearest integer. You should choose an appropriate and efficient algorithm to obtain the shortest route from station S to D. If there are more than one shortest route, the route with minimal cost C should be used.

根据题目描述，可以等价为在二维有向图中，从某一点出发至另一个点的最短路径问题。Dijkstra算法适用于类似权重为正的最短路径问题中。

算法模版

构造check数组与dis数组，分别记录节点是否完成探索以及当前距离，在初始化时，需要将dis赋值为正无穷代表无法抵达。算法从第一个点出发，遍历所有边，并更新两点之间的距离，通过排序找到与这个点距离最短的点（即dis中未check的点中距离最小的点）标记并作为下一次迭代的依据点。

void dijkstra()
{	
		for 1 to n: dis = inf;
  	for(int i=1;i<=n;i++){
      	for 寻找所有可行路径
          	如果新路径比旧路径更短，更新dis
        for 寻找最小值
          	设置出发点
    }
}

在模版中，循环主体设置为1到n次，若遇到已知有不通的路径则另作处理。下图为算法实现的实例，假设从0点开始：

1. 标记阶段0，寻找通路 0-1，0-2，由于两个距离均小于正无穷，更新dis；寻找最小值节点1，并标记1

Dis	0	1	2	3	4	5	6
	0	2	6	inf	inf	inf	inf