[Tutor] distance between cities matrix

[Danny Yoo]

> Consider the (20x20) array of numbers here(I wrote all of the numbers in
> my program). Lets say this represents a matrix A of distances (in
> kilometers) between cities. Note that A is symmetric A(i,j) = A(j,i) and all
> its diagonal elements are zero. Suppose Vladimir from city i and Petra from
> city j want to meet up in some third city k (i, j and k are all different).
> Conscious about their carbon footprint (!), they want k to be as near as
> possible: specifically the sum of the distances both has to travel should be
> minimum. Given i and j, write a program in PYTHON that determines what k
> should be.

This sounds like a fairly straightforward CS graph algorithms question.

Is there a unique meeting point k that satisfies these conditions, or
can there be several possibilities?

How is this problem different from a standard shortest-path search?
Ah, I think I see it.  I'm assuming the difference is that it's in the
shape of the legal solutions.  Solutions  must be in the form of only
two direct hops:

    from i to k, and
    from k to j

and not some path of arbitrary length.


You ask the question: how do I test this?  Here's one approach: create
your own simple distance matrix for a very small map that you
construct.  Make your own test data.  Have it have four cities (or
fewer!).  That way, you can know in advance what the answer is
supposed to be for any two pairs.  Then you can write test cases and
see that your algorithm is doing what you expect it to.