Formula that calculates the distance between origin -> destination#1 -> destination#2 and so on.

[Terar]

Hi there!

I wonder if anybody knows a formula that will calculate the distance between origin and multiple destinations. For example:

Origin: A //is only one origin.

Destinations: B, C, D, E. /I have got 20 destinations.

A -> B, A -> C, A -> E. //that's the distance between origin and each destination. I have it in m/km.

What I want to do is next:

A ->B, B ->C, C -> D, D ->E. //Basically calculate the distance between one place and another.

Also, how would I represent that in a graph like this:

A = origin	B = d#1	C = d#2	D = d#3
B = d#1	0
C = d#2		0
D = d#3			0

I don't know how to calculate the value and insert it in the empty slots.

I need this for a project that I have at the uni. Thank you!

 

[Dr.Peterson]

If you know the distances from A to B and from A to C, you don't know enough to find the distance from B to C. It could be anything between the difference between AB and AC and the sum of AB and AC. And that's assuming straight line distances. Road distances could vary even more; and there might be different routes to consider, too.

Why do you think this could be done? Why do you need to do it? What kind of mathematics or other subject are you studying?

 

[Terar]

I am studying computer science and yes, I reviewed my plan and yeah, it seems that I missed some bits. I am not really good at maths atm but what I figured now out is that what I need is a matrix lets say in my case is 10 cities. I need to find the shortest path from one to another. I have these 10 cities and I know the distance between each pair. Now, I would like to confirm and ask if it's possible to create a graph out of it:

let's say:

A -> B -> C -> D ->E
B 0 - - -
C - 0 - -
D - - 0 -
E - - - 0

Is this a correct representation considering that I know the distance between each pair of cities?

 

[Dr.Peterson]

I was wondering why you called your table a graph. Evidently you are trying to make a graph in the sense of graph theory. But there are several types of graph even within that realm; they can be directed or undirected, it can be allowed to have more than one edge joining any pair of nodes, or to have an edge between a node and itself, and so on. In any case, you are presumably talking about a weighted graph, where each edge is associated with a distance.

What we need to know is what your actual assignment is! What are you ultimately given, and what do you need to find out? Also, what have you been taught that you are expected to use (e.g. about graph theory, or about representations)?

A table like you showed must be half filled in (say, all entries above the diagonal, in order to know the distance between every pair of cities; you may have seen such tables in road atlases. We can't fill in any entry from any or all other entries. If you used a complete table (or matrix), it would have to be symmetrical.

Are you now saying that you will be given such a graph, and are to find the shortest path (which can go through other cities) from any one city to another?

 

[Terar]

Yes, correct! The complete table(or matrix) will be symmetrical. And yes I am about to find the shortest path from any one city to another.

 

[Dr.Peterson]

Then your real question will be what representation to use in your program for the data, and how to use that in an algorithm. Presumably, you have been taught something about both data representations and algorithms; I don't know what help you need without such background information.

But to answer your original question, this is not a mere "formula", but an algorithm, which is up to you. In some sense, the algorithm will just add up the lengths of edges for each possible path.