图的最短路径问题
请问一下 在 完成最短算法后 怎么样输出最短路径 多经过的点啊
急 急 急
搜索更多相关的解决方案:
路径
----------------解决方案--------------------------------------------------------
如果你是用dijkstra算法的话，在每次扩展点的时候记录这个点的在最短路上的前驱点，最后逆向找最短路就可以了
----------------解决方案--------------------------------------------------------
如果用FLOYD算法 呢
----------------解决方案--------------------------------------------------------
floyd算法的话我目前想到的需要三维数组
假设有MAX个节点
用
flag[MAX][MAX][MAX]；flag[某路径起始点标号][该路径终止点标号][T]该最短路上T的后继节点（如果T不在该路上可以特殊处理，比如标记为-1）具体处理在floyd扩展的时候很容易做到，
当最大路过标号为k时,如果该路径不过k，显然不用做任何修改，如果过的话，就把k的前驱节点和k本身的信息修改一下就可以了
----------------解决方案--------------------------------------------------------
不好意思，上面那楼说的方法应该错D
----------------解决方案--------------------------------------------------------
找一本图论的书看吧！
----------------解决方案--------------------------------------------------------