论文部分内容阅读
[摘 要]给出一种无向简单图最短路径运算的方法,通过求得简单无向图任意两顶点间的最短距离,此方法经单易懂,但是运算量较大,无向图的最短路径实现相对于带权的有向图最短路径实现要简單得多。
[关键词]矩阵运算;最短路径;无向简单图
中图分类号:TUO158 文献标识码:A 文章编号:1009-914X(2017)45-0265-01
[Abstract]Given a simple undirected graph shortest path computation method, obtained by simple undirected graph shortest distance between any two vertices, this approach via single and easy to understand, but the computational cost is larger, undirected graph shortest path to implement relative to the weighted directed graph shortest path implementation is much more simple.
[Key words]Matrix operations; Shortest path; Undirected graph
3 结论
通过这种方法求得无向图任意两顶点的最短距离.可以应用到管道铺设、交通网络、线路安排、设备更新等很多领域中。本算法为求路径的最优化问题提出了方法。
参考文献
[1] 耿素云,屈婉玲.离散数学[M].北京:北京大学出版社,2002.157-167
[2] 李刚.离散数学[M].上海:复旦大学出版社,2006.225-249
[3] 李蔚萱.图论[M].长沙:湖南科学技术出版社,1980.91-11.5
[4] 董洁磐.离散数学导论[M].北京:高等教育出版社,1991.149—162.
作者简介
袁威威,(1982—),女,黑龙江黑河市人,黑河学院理学院教师,从事数学与应用数学,图论研究。
[关键词]矩阵运算;最短路径;无向简单图
中图分类号:TUO158 文献标识码:A 文章编号:1009-914X(2017)45-0265-01
[Abstract]Given a simple undirected graph shortest path computation method, obtained by simple undirected graph shortest distance between any two vertices, this approach via single and easy to understand, but the computational cost is larger, undirected graph shortest path to implement relative to the weighted directed graph shortest path implementation is much more simple.
[Key words]Matrix operations; Shortest path; Undirected graph
3 结论
通过这种方法求得无向图任意两顶点的最短距离.可以应用到管道铺设、交通网络、线路安排、设备更新等很多领域中。本算法为求路径的最优化问题提出了方法。
参考文献
[1] 耿素云,屈婉玲.离散数学[M].北京:北京大学出版社,2002.157-167
[2] 李刚.离散数学[M].上海:复旦大学出版社,2006.225-249
[3] 李蔚萱.图论[M].长沙:湖南科学技术出版社,1980.91-11.5
[4] 董洁磐.离散数学导论[M].北京:高等教育出版社,1991.149—162.
作者简介
袁威威,(1982—),女,黑龙江黑河市人,黑河学院理学院教师,从事数学与应用数学,图论研究。