图的最短路径和传递闭包的并行算法 |
| |
引用本文: | 马军,高冈忠雄.图的最短路径和传递闭包的并行算法[J].计算机学报,1990,13(9):706-708. |
| |
作者姓名: | 马军 高冈忠雄 |
| |
作者单位: | 山东大学计算机科学系
(马军),日本国茨城大学工学部情报工学科(高冈忠雄) |
| |
摘 要: | 1.图的最短路径 给定一赋权有向图G=(V,E),假设G中没有带负权圈的顶点,Floyd给出了一个计算G的所有顶点对v_i,v_j之间最短路径算法。在该算法中,用带权邻接矩阵cosT表示图,并规定cosT(i,j)=∞若(i,j)不属于E和cosT(i,j)=0,i,j=0,…,n-1,该算法的设计思想是按下面的递推规则依次产生矩阵序列A~0,…,A~(n-1),其中A~(n-1)即是G的所有顶点对之间最短路径的长度。
|
关 键 词: | 图 最短路径 传递闭包 并行算法 |
本文献已被 CNKI 维普 等数据库收录! |
|