小弟学店资工系 简单介绍一下这个算法
作者在文中已经有提到是dijkstra's algorithm 戴克斯奥拉算法
主要用在最短路径的探讨上
其实可以应用在很复杂的铁路系统
可惜台湾高铁连一圈都没有连起来 所以简单很多
范例影片 https://www.youtube.com/watch?v=5GT5hYzjNoo&t=5s
我们拿高铁台北站来作范例
影片中会有无限符号可以想成无法直接买到那站的车票 要转车所以暂时是未知
票价图
http://imgur.com/K7isTxw
先把台北站可以到达的票价都先列出来
http://imgur.com/FOe9ktS.jpg
这是从台北坐到各站的价钱
台北->南港再到各站的价钱 比对之后没有比较便宜的 所以照抄下来
台北到南港已经是最便宜 用红色底标注
http://imgur.com/JkfckeI.jpg
然后比对从台北->板桥 再到各站的价格有无较便宜
刚刚忘记放数据了 这里开始会放 未标注地名的是代表台北到该站再到各站的价钱
像下图是台北到板桥再到各站 (台北到板桥:40 + 板桥到各站:x)
有标注地名的是表示从哪一站过来的
http://imgur.com/jbwwya3.jpg
所以可以看到从台北直达还是都比较便宜
下一站 桃园
台北->桃园->各站
http://imgur.com/rFdOmkp.jpg
这里可以看到某些站的价格已经打平了
不过打平还不够
http://imgur.com/NbdF4Qy.jpg
下一站 新竹
台北->新竹->各站
http://imgur.com/fw24NFz.jpg
还是打平的状态
下一站 苗栗
各位同胞们我们在台北->苗栗->嘉义终于省了10块钱啦(用蓝色标注
http://imgur.com/5ArhDaB.jpg
所以嘉义那边地名改成苗栗 以后到嘉义都要先到苗栗转车
苗栗忘记打出来了= ="
下一站 台中
还是打平 这边要注意到嘉义都要在苗栗转车 所以到嘉义路径是
台北->苗栗->台中->嘉义
http://imgur.com/IY7W54s.jpg
下一站 彰化
还是一样 数据忘记截= =" 抱歉
http://imgur.com/NRoNMMJ.jpg
下一站 云林
http://imgur.com/KAKClN9.jpg
还4一样
http://imgur.com/Pat5ivk.jpg
下一站 嘉义
由于前面知道 台北到嘉义在苗栗转车会比较便宜 所以剩下的台南和高雄都会在苗栗转车
也就是 台北->苗栗->嘉义->各站 这样子
http://imgur.com/pMFUDvp.jpg
左营再便宜了10元
下一站 台南
http://imgur.com/qPVVWyR.jpg
没有比较便宜
http://imgur.com/ouAOTQh.jpg
所以根据dijkstra's 算法
台北->苗栗->嘉义->左营
这样转车到左营的确可以便宜20元
不过这是没有考虑时间的问题
如果考虑进时间的话
相信绝对还是是台北高雄直达CP值最高的
在此做个简单的介绍 有误还请指正
如果变成考题学弟妹不要怪我030
作者:
shiburin (废文制造机)
2017-08-15 14:32:00嗯跟我想的一样
作者:
mcmcmc (mcmcmc)
2017-08-15 14:34:00操作不难 难的是证明为何是对的
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 14:34:00高铁路线基本上只是一条炼 看不出Dijkstra's的特点
作者:
seuil ( )
2017-08-15 14:35:00算法厉害 可以算出便宜20元 跟我用纸笔算的一样
作者:
wemee (方天画)
2017-08-15 14:35:00楼下跳针贪婪法则跟旅行背包解高铁问题
作者:
hipab (嗨趴)
2017-08-15 14:40:00楼下负cycle shortest path 让高铁无限循环
作者:
fate201 (Licht)
2017-08-15 14:52:00每条路的票价当成距离就好了 最终移动距离都相同啊
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 14:53:00楼上 你有听过最短路径树吗还一张网勒...
…台北到台中，台中再到高雄，和台北到高雄是三条线讲这样够白了吧…
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 14:56:00不是很明白你想表达什么 Dijkstra's只会留下到某个点
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 14:57:00这求的是单源最短路径 我想你指的是all pairs
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 15:00:003楼? 你现在是在想证明吗
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 15:02:00这样说好了 假设a到b有5种相异路径 成本不尽相同算法跑完 只会留下一种成本最低的路径 其他的都不管单源最短路径的情况下啦假设起点就是a 那Dijkstra's一旦走到了b 走法肯定是成本最低 所以之后再有路径可以到b都无视 因为不会改善a到b 或是a经过b到其他点的距离在一条炼的情况下这看不出来 因为只会一直往前钻
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 15:08:00哦应该说我错了 这不算是一条炼 因为各站间可以直达我误会你了 你是对的
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 15:09:00所以原图的确是一张网 不是一条炼
作者: zzzz8931 (肥宅) 2017-08-15 15:18:00
时间复杂度？