Как найти кратчайшую стоимость пути?

Обновить

April 2019

Просмотры

1.4k раз

1

У меня есть два массива

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

и так on..total 16 (2 ^ 4) такая комбинация будет отображаться.

Я refereing некоторые вопросы в SO + другие, но не в состоянии понять.

Как это сделать, не принимая помощи какой-либо третьей библиотеки partry? И, пожалуйста, обеспечивают легкий способ сделать это !!

Моя попытка (не очень правильно)

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); 

введите описание изображения здесь

Заранее спасибо.

3 ответы

1

First, create a mapping between city and cost, so we can easily access the cost of each edge:

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 now looks like

enter image description here

Now that we have an appropriate data structure, finding the path costs is trivial:

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
0

You can redefine your nodes something like this

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

And then traverse this 2d array to run through all combinations. Saving data in 2d array might simplify the way you need to know costs.

And when you say

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

It is actually you are starting at A, going to B, then C and finally ending up on D.

[Totally blank now, could have given you some sample code to run through it. Forgive me for that]

0

As I said in the commet above the only way to be able to know the EXACT value is by going through all combinations.

In university on Graph Theory I did something like this

   A   B   C   D
A  -   2   3   1

B  2   -   2   4

C  3   2   -   3   

D  1   4   3   -

Now you just have to compute all possibilities I like to do it like this

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

You assign each solution the correct weight and pick the one which is shortest.