在数据结构程序设计中,我选择弗洛伊德算法用以计算出任意两城市间的最小花费,同时表示出途径城市,这样在计算花费最少时会非常便捷。弗洛伊德算法其实并不复杂,在写弗洛伊德算法时要对图有熟悉的了解。可以参考Floyd算法——C++实现版这篇文章,注意要有Path的二维数组记录路径,我是这样理解的:i和j之间途经k“路径”最短(双引号的意思是,这里的路径还可以表示其他权值),而k和j之间可能通过其他节点m实现更短的路径......直到最后的点n和i表示同一点为止,这便是两个城市之间最短路径所要途径的城市。当然,这是一个递归的过程,也可以使用C++的STL stack来表示,把首尾节点以及中间节点都压入栈中,打印的时候再不断地弹栈,此处知识可以参考C++ stack中的相关知识。
实现算法后要把源代码添加到文章中。
网友评论