类Dijkstra算法问题求解
设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是
单向的,这n个车站被顺序编号为0至n-1.本程序, 输入该城市的公交线路
、车站个数,以及各公交线路上的各站编号,求得从站0出发乘公交车至第
n-1站的最少换车次数？
给出算法并代码！
问题点数：100、回复次数：7Top
1 楼Zephyrzzz（）回复于 2006-03-04 01:03:11 得分 0
每次在n个车站找出最小的未标号的顶点进行扩展,复杂度是O(nm).Top
2 楼yelling（Ray（←☆→射手））回复于 2006-03-04 10:13:23 得分 0
已经是经典的Dijkstra问题了，还要代码？Top
3 楼liuyi1982（kiki）回复于 2006-03-04 19:48:19 得分 0
最少换车次数,而不是路径长短问题
这不是Dijkstra算法
而是图的广度优先遍历法Top
4 楼ShowLovE（天天）回复于 2006-03-04 23:00:38 得分 0
权为1的Dijkstra不行么Top
5 楼yunxiang_yang（Spirit163）回复于 2006-03-04 23:23:36 得分 0
我的思路：当作图的遍历，寻找可能的路线，对于每一种路线，从站0开始，选择一条路线时对设定的基数器加1，直到达到第n站！然后比较各种路线计数器，选最小者再减1！Top
6 楼yunxiang_yang（Spirit163）回复于 2006-03-04 23:35:12 得分 0
只能说是图的一部分经过，但也不是Dijkstra算法！
大家说是否？Top
7 楼yunxiang_yang（Spirit163）回复于 2006-03-04 23:59:32 得分 0
权为1的话可以考虑，但是能达到的路线都是最短路径，比较换车次最少应该还得进一步考虑！
注意一条线路不一定要全部走完！Top
