دانلود مقاله ISI انگلیسی شماره 79204
ترجمه فارسی عنوان مقاله

دو الگوریتم سریع وکوتاه ترین مسیربرای همه زوج ها

عنوان انگلیسی
Two fast algorithms for all-pairs shortest paths
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
79204 2007 16 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Computers & Operations Research, Volume 34, Issue 9, September 2007, Pages 2824–2839

ترجمه کلمات کلیدی
کوتاه ترین مسیر - معادلات بلمن، گراف بدون دور جهت
کلمات کلیدی انگلیسی
Shortest paths; Bellman equations; Directed acyclic graph
پیش نمایش مقاله
پیش نمایش مقاله  دو الگوریتم سریع  وکوتاه ترین مسیربرای همه زوج ها

چکیده انگلیسی

By scanning the arcs in order of increasing weight, arcs are eliminated earlier. By scanning the nodes in a ‘pseudo-topological’ order, the computation time can further decrease. In acyclic directed networks one of the resulting all-pairs algorithms runs in O(mlogn+nm0)O(mlogn+nm0) time, where m0m0 denotes the number of ‘essential’ arcs, i.e., arcs that are indispensable in some shortest path.