如何找到最短路徑成本？

我有兩個陣列如何找到最短路徑成本？

string[] city = {"A","B","C","D"}

和連接的成本他們說

int[] cost ={ 2,1,3,2,4,3}

的任務是找到這將是6這裏的最短路徑成本。

爲什麼？

A->B = 2 
A->C = 1 
A->D = 3 
--------- = 6 (cheapest) 

B->C = 2 
B->D = 4 
B->A = 2 
-------- = 8 

C->D = 3 
C->A = 1 
C->B = 2 
------------ = 6 (cheapest) 

D->A =3 
D->B = 4 
D->C = 3 
------------- = 10

等等..總數16（2^4）這樣的組合會出現。

我正在引用SO +中的其他一些問題，但無法理解。

如何做到這一點，而不需要任何第三方圖書館的幫助？請提供一個簡單的方法來做到這一點！

我嘗試（不是很正確）

public static int minimum_cost(string[] input1, int[] input2) 
{ 
    int i = 0; 
    int j = 0; 
    int k = 0; 
    int counter = 0; 
    int len = input2.Length; 
    var storage = new int[input1.Length * input2.Length]; 

    for (i = 0; i < len - 2; i++) 
    { 
     for (j = i + 1; j < len - 1; j++) 
     { 
      for (k = j + 1; k < len; k++) 
      { 
       var m1 = input2[i]; 
       var m2 = input2[j]; 
       var m3 = input2[k]; 

       storage.SetValue(m1 + m2 + m3, counter);      
       counter++; 
      }     
     }    
    } 
    return storage.Take(counter).Min(); 
}

調用

var input1 = new string[] { "A", "B", "C", "D" }; 
var input2 = new int[] { 2, 3, 1, 2, 4, 3 }; 
var res = minimum_cost(input1, input2);

enter image description here

在此先感謝。

來源

2013-05-10 priyanka.sarkar

您的代碼並沒有太大的意義沒有上下文。例如，您的6個整數成本代表哪些連接？我理解你的目標是一個所有節點都連接的圖表嗎？ – 2013-05-10 11:46:43

您的示例輸出不顯示最短路徑，而是最中心的城市。最短的路徑將依次通過所有城市，因此不會出現「A-> B，A-> C，A-> D」，而是「A-> B，B-> C，C-> D」。 – 2013-05-10 11:47:53

@ Dan Puzey，是的，先生...你可以假設他們連接在圖中... – 2013-05-10 11:47:55

首先，創建city和cost之間的映射，所以我們可以很容易地訪問每個邊的成本：

string[] city = {"A","B","C","D"}; 
int[] cost = {2,1,3,2,4,3}; 

var mappings = new List<Tuple<string, string, int>>(); 

var cs = new Queue<string>(city); 
var e = cost.GetEnumerator(); 
while(cs.Any()) 
{ 
    var c = cs.Dequeue(); 
    foreach (var o in cs) 
    { 
     e.MoveNext(); 
     mappings.Add(Tuple.Create(c, o, (int)e.Current)); 
    } 
}

mappings現在看起來像

enter image description here

現在，我們有一個適當的數據結構，尋找路徑成本微不足道：

var result = from c in city 
      select new { c, cost = mappings.Where(m => m.Item1 == c || m.Item2 == c).Sum(m => m.Item3) };

enter image description here

var shortest = result.Min(a => a.cost); // 6

來源

2013-05-10 12:21:57 sloth

你可以重新定義你的節點是這樣的

A B C D 
A - 2 1 3 
B 2 - 2 4 
C 1 2 - 3 
D 3 4 3 -

然後遍歷這個二維數組通過所有組合運行。將數據保存在二維數組中可能會簡化您需要了解成本的方式。

當你說

A->B = 2 
A->C = 1 
A->D = 3 
--------- = 6 (cheapest)

它實際上是你從A開始，將B，然後是C，最後D上結束了

[全白了，本可以給你一些示例代碼來貫穿它。請原諒我]

來源

2013-05-10 11:55:01 Yahya

正如我在上面的commet中所說的，唯一能夠知道EXACT值的方法是通過所有組合。

在圖論的大學，我做了這樣的事情

A B C D 
A - 2 3 1 

B 2 - 2 4 

C 3 2 - 3 

D 1 4 3 -

現在，你只需要計算所有可能我喜歡做這樣

[A B C D] 
[A B D C] 
[A C B D] 
...

可以爲每個解決方案正確體重並挑選最短的一個。

來源

2013-05-10 11:58:11

如何找到最短路徑成本？

回答

相關問題