选定以下字段即可查看[color=red]（请各位OIER自我约束！待比赛结束后再查看）[/color]
[color=white]
所谓带限制条件的最短路径是指满足用户约束条件的最短路径.用户的约束条件是:给定起始节点(start)和目标节点(end)以及该路径上的避开节点列B={B1,B2,…,Bn}和必经节点列J={J1,J2,…,Jn.
若要避开某些节点,则可在改进的Dijkstra算法中加入判断语句,即当从堆中抽出具有最小D值的点并标记已访问时,判断该点是否是避开节点列中的点,若是则不入红点集.
若需经过某些节点,则利用分段求最短路径的方法求出总的最短路径.可将J存成一个数组,用改进的Dijkstra算法先算起始节点start与J[0]的最短路径,然后对数组下标i进行循环,判断下一个节点是否是已经过节点,若是继续数组下一个节点,否则调用Dijkstra算法计算J[i]与该节点的最短路径,然后再以该节点为起始节点重复上述判断直到数组最后一个元素,最后计算它与终点end的最短路径,再将所求得最短路径值相加即得总最短路径值.要值得注意的是每次在调用Dijkstra算法之前,要重新将所有的点设置为未访问过(UNVISTED),因为算法结束时很多点都已访问过(VISITED).而且要把各段所计算出的最短路径D值以及经过的点保存起来.
本题为限制必经节点的最短路径。
[/color]
如有缺漏，欢迎指出
by AKB48 @ 2013-10-03 21:44:32