न्यूनतम प्राथमिकता कतार

Question

के साथ डिजस्ट्रा एल्गोरिदम मैं प्राथमिकता कतार के साथ डिज्कास्ट्रा एल्गोरिदम लागू करने की कोशिश कर रहा हूं, लेकिन मुझे समझ में नहीं आता कि यह कैसे काम करता है। मैंने वेब पर कई मार्गदर्शिकाएं पढ़ी हैं लेकिन मैं इस एल्गोरिदम को बिल्कुल समझ नहीं पा रहा हूं।

मेरा प्रश्न है: प्रत्येक नोड के लिए प्राथमिकता क्या है? मुझे लगता है कि यह आने वाले किनारे का वजन कम से कम मूल्य के साथ है, लेकिन मुझे यकीन नहीं है। क्या ये सच है?

दूसरा प्रश्न, जब मैं कतार की जड़ निकालने के लिए, यह कैसे काम करता है अगर यह नोड किसी न किसी नोड के साथ निकटता नहीं है?

Answer 1

आपको priority queue का उपयोग करना चाहिए जहां vertexvertex से सबसे कम दूरी के साथ उच्च प्राथमिकता प्राप्त करेगा। प्रारंभ में, सभी vertices अनंत की कम से कम दूरी और PQ अंदर ग्राफ से (अपने edges के साथ) सभी vertices के डालने से शुरू करने vertex कम से कम दूरी होगा 0.

प्रारंभ होगा। PQ से vertex निकालें और अपने सभी edges का पता लगाएं। सभी निकटवर्ती vertices के साथ सबसे छोटी दूरी की तुलना करें और यदि vertex पर सबसे कम दूरी से कोई दूरी कम है, तो PQ के अंदर निकटतम vertex छोटी दूरी अपडेट करें। जारी रखें जबकि PQ खाली नहीं है। Vertices जो edges नहीं मिला अनंतता की सबसे छोटी दूरी के साथ खत्म हो जाएगा क्योंकि vertex से 'उन्हें प्राप्त करें' संभव नहीं है। हालांकि, उन्हें अभी भी PQ से निकाल दिया जाएगा।

स्यूडोकोड

initialize graph 
initialize pq 
pq.insertAll(graph.getVertices()) 

while (pq is not empty) { 
    vertex = pq.remove() 
    edges = vertex.getEdges() 

    for all edges { 
    destination = edge.getDestination() 
    newDistance = edge.getLength() + vertex.getDistance() 
    if (newDistance < destination.getDistance()) { 
     destination.setShortestDistance(newDistance) 
     pq.update(destination) 
    } 
    } 
} 

एमआईटी ओपन कोर्स वेयर लिंक:
Path problems overview
Dijkstra