Ideas to represent such a case

Question

I am designing a flight simulation program and I am looking for ideas on how to properly implement such requirement.

Kindly look at my picture below. The points represents location.

The idea is this, I wanted to properly create a data structure to best represent such scenario in java such that

• when I am in Point 1, how far I am from the last point which is Point 8?

  • Points 2, 3 and 5 are at the same distance from Point 8
  • From Point 1, I could traverse to Point 3 to Point 6 then 7 then eight that would equate to 4 Steps.

• when I am in Point 0

  • I could traverse to Point 4 then 5 then 7 then reach point 8 which would equate to 4 steps also.

I just wanted to assist user to help them find different route.

Is this possible and which java data structure should best fit this requirement? Also any design ideas how to implement this?

Sorry if my question might be vague, I am just trying to get as much information as I can to properly handle such requirement.

Answer 1

This is a Shortest Path problem, a common Graph problem. The usual way to represent the data is an Adjancency List or Matrix:

An adjancency list keeps, for every node, all 1-step reachable destinations. This is often implemented as a Linked List. It's the proper choice if your graph is relatively sparse (i.e. few destinations per node).

An adjancency matrix is used for (very) dense graphs. Basically, you keep an NxN matrix of values (weights/costs, or yes/no booleans). Then, distances[i][j] represents the cost of travelling to j from i. An unavailable arc has a cost of INF (or some error value).

The problem itself is generally solved by Dijkstra's Algorithm.

Answer 2

What you have is a weighted graph where the weights represent the distance between the nodes (which is very common). You could easily implement this yourself (and it's a great way to learn!), but there are lots of java source code for this out there.

Of course, this is not a java data structure. It's simply a data structure (or a concept), used by everyone, everywhere.

Calculating steps and distances is very easy once you've implemented a weighted graph.

There are massive amounts of documentation on all of this, especially here on Stackoverflow.