How to find the shortest path cost?

Question

I have Two Arrays

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

And the cost of connecting them say

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

The task is to find the shortest path cost which will be 6 here.

Why?

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

and so on..total 16(2^4) such combination will appear.

I am refereing some questions in SO + others but not able to understand.

How to do it without taking help of any third partry library?And please provide an easy way of doing so!!

My attempt(not very correct)

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

Invocation

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

Thanks in advance.

Answer 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

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

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

Answer 2

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.

Answer 3

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]