s-t paths using the min-sum algorithm
s-t paths using the min-sum algorithm
复制标题
使用最小和算法的 s-t 路径
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
S. Tatikonda
中科院分区：
文献类型：
--
作者：
Nicholas Ruozzi;S. Tatikonda
求解分布式最短路径问题在分布式系统理论中有重要的应用，最著名的是路由。本文给出并证明了边权为正数的图中两点间最短路的最小和算法的收敛性。与标准的分布式最短路径算法不同，收敛速度取决于最小路径的权重，而不一定是网络中的节点数。
Solving the distributed shortest path problem has important applications in the theory of distributed systems, most notably routing. In this paper, we provide and prove the convergence of a min-sum algorithm to compute the shortest path between two nodes in a graph with positive edge weights. Unlike the standard distributed shortest path algorithms, the rate of convergence depends on the weight of the minimal path and not necessarily the number of nodes in the network.