डिजस्ट्रा एल्गोरिदम

Question

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

private int[] Dijkstra(int start, int end) 
    { 
     bool[] done = new bool[8]; 
     int[] parent = new int[8]; 
     for (int i = 0; i < parent.Length; i++) 
      parent[i] = -1; 
     int[] distances = new int[8]; 
     for (int i = 0; i < distances.Length; i++) 
      distances[i] = int.MaxValue; 
     distances[start] = 0; 
     int current = start; 
     while (!done[current]) 
     { 
      done[current] = true; 
      for (int i = 0; i < 8; i++) 
      { 
       if (graph[current, i] != int.MaxValue) 
       { 
        int dist = graph[current, i] + distances[current]; 
        if (dist < distances[i]) 
        { 
         distances[i] = dist; 
         parent[i] = current; 
        } 
       } 
      } 
      int min = int.MaxValue; 
      for (int i = 0; i < 8; i++) 
      { 
       if (distances[i] < min&&!done[i]) 
       { 
        current = i; 
        min = distances[i]; 
       } 
      } 
     } 
     return parent; 
    } 

यह काम करता है, लेकिन, फिर भी मैं नहीं जानता कि कैसे, यह के बीच सबसे छोटा मार्ग प्राप्त करने के लिए उदाहरण 1 और 3 के लिए, और 1 की तरह मार्ग लौट => 4 => 2 => 3।
अग्रिम धन्यवाद। http://quickgraph.codeplex.com/ (NuGet के माध्यम से भी उपलब्ध है)

Answer 1

Djikstra के एल्गोरिथ्म शुरू से अंत करने के लिए कम से कम पथ को ट्रैक करने के लिए माता-पिता सरणी का उपयोग करता है:

Answer 2

QuickGraph समाधान का प्रयास करें। आप माता-पिता [अंत] से शुरू करेंगे और सरणी की प्रविष्टियों का पालन करेंगे जब तक कि आप वापस शुरू नहीं कर लेते।

कुछ स्यूडोकोड:

List<int> shortestPath = new List<int>(); 
int current = end; 
while(current != start) { 
    shortestPath.Add(current); 
    current = parent[current]; 
} 

shortestPath.Reverse(); 

है कि आपको बस के बारे में अपने कार्य के साथ है या नहीं, आरंभ और अंत मूल्यों में पारित उचित मान रहे हैं (या नहीं, वे वास्तव में अपने ग्राफ़ के कोने का प्रतिनिधित्व चिंता करने की ज़रूरत , उदाहरण के लिए)।

Answer 3

एक बार जब आप गंतव्य चरम पर पहुंच जाते हैं तो आप मूल मैट्रिक्स का उपयोग कर प्रारंभिक चरम पर पथ को पीछे हट सकते हैं। कुछ ऐसा (स्रोत से dest तक पथ है):

void backtrack(int source, int dest, vector<int> &path) 
{ 
    path.push_back(dest); 

    for(int vertex = parent[dest]; vertex != source; vertex = parent[vertex]) 
    path.push_back(vertex); 

    path.push_back(source); 
} 

नोट: पथ विपरीत क्रम में होगा।