专注于互联网--专注于架构

单源最短路径:C语言算法之单源最短路径

在这个问题中给出有向图G它每条边都有个非负长度(耗费) a [i ][ j ]路径长度即为此路径所经过边长度的和对于给定源顶点s需找出从它到图中其他任意顶点(称为目)最短路径图13-10a 给出了个具有 5个顶点有向图各边上数即为长度假设源顶点s 为1从顶点1出发最短路径按路径长度顺序列在图13-10b 中每条路径前面数字为路径长度 利用E. Dijkstra发明贪婪算法可以解决最短路径问题它通过分步思路方法求出最短路径每步产生个到达新目顶点最短路径下步所能达到目 [阅读全文] [PDF]