shortest path in hash map

Question

The following is a data set I have stored in a hash map, and I have to find the shortest path between two values.

9244, 4322, 4886, 5989, 8598, 9979, 1447, 9657
8598, 6752, 7146, 1951, 660, 1447, 7779
568, 1951, 4886, 2570, 9026, 9489, 7779
6752, 3424, 1977, 4746, 9657
77

The key value of the hash map is the first value of each line, the rest are the supposed "friends" of 9244 (same in each case).

i have saved in hash table in this format: hashmap(key, array), where:

• key is e.g. 9244
• array then holds [ 4322, 4886, 5989, 8598, 9979, 1447, 9657 ]

How to find shortest path between two keys?

Answer 1

You can implement the A* algorithm. You can build a graph out of this first and then follow the pseudocode on the wikipedia page.

Answer 2

If I interpret your question correctly, you're talking about the Shortest Path problem with a directed graph.

• Starting with an integer, get the array of integers it maps to.
• Each of those integers is the key to a new array.
• Follow those paths and find the shortest one.

If you do a google search, and look on the Wikipedia page, you'll be able to find plenty of code samples and algorithms that will help you.

As Peter Smit mentioned, the A* algorithm is a common one for this problem. Others include Dijkstra's and Bellman-Ford.