ग्राफ सिद्धांत: जॉर्डन केंद्र खोजें?

Question

मैं उन शिखरों का सेट ढूंढने की कोशिश कर रहा हूं जो भारित ग्राफ पर अन्य अक्षरों तक उनकी दूरी को कम करता है। एक कर्सर विकिपीडिया खोज के आधार पर, मुझे लगता है कि इसे Jordan Center कहा जाता है। इसे खोजने के लिए कुछ अच्छे एल्गोरिदम क्या हैं?

अभी, मेरी योजना प्रत्येक शाखा एक दिया शिखर से उत्पन्न के लिए वजन की एक सूची प्राप्त करने के लिए है। जिन शिखरों का वजन सबसे छोटा सा रिश्तेदार अंतर होता है वह केंद्रीय होंगे। कोई अन्य विचार?

मैं जावा का उपयोग कर रहा हूं, लेकिन उपयोगी उत्तरों को जावा विशिष्ट होने की आवश्यकता नहीं है। ग्राफ केंद्र समस्या के लिए

Answer 1

मैं वर्टिकल के सभी जोड़े के बीच सबसे कम दूरी computng के लिए पहली बार उपयोग Dijkstra algorithm (यह प्रत्येक verticle के लिए चलाने के लिए है) woluld - वहाँ भी कर रहे हैं कि Floyd-Warshall तरह के लिए कुछ और कुशल एल्गोरिदम। फिर प्रत्येक वर्टिकल वी के लिए आपको Vm - सबसे बड़ा डेटा को पुन: डिज़ाइन किए गए डेटा डिजस्ट्रा एल्गोरिदम के बीच किसी अन्य वर्टिकल से दूरी प्राप्त करना होगा। फिर, सबसे छोटे Vm के साथ लंबवत ग्राफ़ केंद्र में से एक हैं। स्यूडोकोड:

int n = number of verticles; 
int[][] D = RunDijkstraOrWarshall() 
// D[a,b] = length of shortest path from a to b 
int[] Vm = new int[n]; 
for(int i=0; i<n i++) 
{ 
    Vm[i] = 0 
    for(int j=0; j<n; j++) 
    { 
    if (Vm[i] < D[i,j]) Vm[i] = D[i,j]; 
    } 
} 

minVm = int.Max; 
for(int i=0; i<n ;i++) 
{ 
    if (minVm < Vm[i]) minVm = Vm[i]; 
} 

for(int i=0; i<n ;i++) 
{ 
    if (Vm[i] == minVm) 
    { 
    // graph center contans i 
    } 

}

Answer 2

तीन एल्गोरिदम इस एमएससी थीसिस में प्रस्तुत कर रहे हैं: A distributed algorithm for the graph center problem।

Answer 3

JGraphT संस्करण 1.1.0 से शुरू, तो आप बस विधि GraphMeasurer.getGraphCenter() उपयोग कर सकते हैं। अंतर्निहित कोड सबसे छोटी पथ विधि का उपयोग करता है। ग्राफ़ की कुछ विशेषताओं (जैसे स्पैस/घने/...) के आधार पर उपयोगकर्ता उपयोग करने के लिए कौन सी विधि का उपयोग कर सकते हैं।