我有两个阵列如何找到最短路径成本?
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);
在此先感谢。
您的代码并没有太大的意义没有上下文。例如,您的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