सबसे अच्छा कम से कम पथ एल्गोरिथ्म

Question

"फ्लोयड-Warshall एल्गोरिथ्म" और "डिज्कस्ट्रा के एल्गोरिथ्म" बीच क्या अंतर है, और जो एक ग्राफ में कम से कम पथ को खोजने के लिए सबसे अच्छा है?

मैं इस प्रकार एक जाल में सभी जोड़ों के बीच सबसे कम पथ की गणना और एक सरणी के लिए परिणाम को बचाने की जरूरत:

**A  B  C  D  E** 
A 0  10 15 5  20 
B 10  0 5  5  10 
C 15  5 0  10 15 
D 5  5 10 0  15 
E 20  10 15 15 0 

Answer 1

Dijkstra के एल्गोरिदम को ग्राफ में नोड और हर दूसरे नोड के बीच सबसे छोटा रास्ता मिलता है। आप इसे प्रत्येक नोड के लिए एक बार चलाएंगे। वजन गैर-ऋणात्मक होना चाहिए, इसलिए यदि आवश्यक हो तो आपको पहले ग्राफ में मानों को सामान्य बनाना होगा।

Floyd-Warshall एक ही रन में नोड्स के सभी जोड़े के बीच सबसे छोटे मार्गों की गणना करता है! साइकिल वजन गैर-ऋणात्मक होना चाहिए, और ग्राफ निर्देशित (आपका चित्र नहीं है) होना चाहिए।

Johnson का एल्गोरिदम एक ही पास में सभी जोड़े को खोजने के लिए डिजस्ट्रा के एल्गोरिदम का उपयोग कर रहा है, और स्पैस पेड़ के लिए तेज़ है (विश्लेषण के लिए लिंक देखें)।

Answer 2

फ्लोयड Warshall कोने के सभी जोड़े के बीच रास्तों पाते हैं, लेकिन डिज्कस्ट्रा केवल पाता है एक कशेरुक से सभी अन्य लोगों के लिए मार्ग।

फ़्लॉइड वॉर्शल ओ (| वी |) और डिक्स्ट्रा ओ (| ई | + | वी | लॉग | वी |) है, लेकिन आपको इसे सभी जोड़े को खोजने के लिए वी बार चलाने होंगे ओ की जटिलता (| ई * वी | + | वी | लॉग | वी |) मुझे लगता है। इसका मतलब है कि एफडब्लू एल्गोरिदम की तुलना में बार-बार डिजस्क्रा का उपयोग करना तेज़ है, मैं दोनों दृष्टिकोणों को आजमाउंगा और देख सकता हूं कि वास्तविक मामले में कौन सा सबसे तेज़ है।

Answer 3

फ्लोयड-Warshall एल्गोरिथ्म प्रयोग करें यदि आप के रूप में यह डिज्कस्ट्रा एल्गोरिथ्म की तुलना में एक (दूर) उच्च चल रहा है समय है, vertexes के सभी जोड़े बीच कम से कम पथ लगाना चाहते हैं।

फ्लोयड-Warshall एल्गोरिथ्म एक सबसे खराब स्थिति हे के प्रदर्शन है डिज्कस्ट्रा के हे की एक बदतर मामले प्रदर्शन के रूप में जहां, (| | वी) (| E | + | वी | लॉग इन करें | वी |)

Answer 4

डिजस्ट्रा को केवल एक वर्टेक्स से सबसे छोटा रास्ता मिलता है, फ्लॉइड-वारशेल इसे के बीच के बीच पाता है।

Answer 5

डिजस्ट्रा मुख्य रूप से एकल जोड़ी सबसे कम पथ खोजने के लिए है, अर्थात एक नोड से अन्य सभी नोड्स तक, जहां फ़्लॉइड-वारशेल सभी जोड़ी सबसे कम पथ के लिए है यानी सभी जोड़ी के बीच सबसे छोटा रास्ता है। फ़्लॉइड-वॉर्शल एल्गोरिदम में ओ (| वी | 3) का सबसे खराब केस प्रदर्शन है, जहां डिजस्ट्रा के ओ (| ई | + | वी | लॉग | वी |) का खराब केस प्रदर्शन है, इसके अलावा डिजस्ट्रा का नकारात्मक उपयोग नहीं किया जा सकता है भार (हम इसके लिए बेलमान फोर्ड का उपयोग करते हैं)। लेकिन फ्लॉइड-वारशॉल के लिए हम नकारात्मक वजन का उपयोग कर सकते हैं लेकिन कोई नकारात्मक चक्र

Answer 6

इस बीच एकल स्रोत सबसे छोटी पथ समस्या के लिए बेहतर एल्गोरिदम ज्ञात हैं। व्यावहारिक रूप से प्रासंगिक एक derivation of Dijkstra's algorithm by Torben Hagerup है। एल्गोरिदम में Djikstra के रूप में एक ही सबसे खराब मामला जटिलता है, लेकिन औसत मामले में अपेक्षित रनटाइम ग्राफ के आकार में रैखिक है, जो शुद्ध डिजस्ट्रा से बहुत तेज है। एल्गोरिदम का विचार इस विचार पर आधारित है कि कतार से न्यूनतम किनारे को हमेशा मतदान करने की आवश्यकता नहीं है।यह संभव है कि कतार से किनारे पर मतदान हो, जिसका वजन 1+k न्यूनतम किनारों के वजन जितना बड़ा होता है, जहां k कुछ संख्या 0 है। यहां तक ​​कि अगर ऐसा किनारा चुना जाता है, तो एल्गोरिदम अभी भी सबसे छोटा रास्ता पायेगा।