кратчайший путь в хэш-карте

Question

Ниже приведен набор данных, который я сохранил в хэш-карте, и мне нужно найти кратчайший путь между двумя значениями.

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

Ключевое значение хэш-карты - это первое значение каждой строки, остальные - предполагаемые «друзья» 9244 (одинаковые в каждом случае).

Я сохранил в хеш-таблицу в этом формате: hashmap(key, array), где:

• ключ, например, 9244
• массив тогда содержит [4322, 4886, 5989, 8598, 9979, 1447, 9657]

Как найти кратчайший путь между двумя ключами?

Answer 1

Если я правильно интерпретирую ваш вопрос, вы говорите о проблеме Кратчайший путь с направленным графом .

• Начиная с целого числа, получить массив целых чисел, с которым он сопоставляется.
• Каждое из этих целых чисел является ключом к новому массиву.
• Следуйте по этим путям и найдите самый короткий.

Если вы выполните поиск в Google и загляните на страницу Википедии, вы сможете найти множество примеров кода и алгоритмов, которые вам помогут.

Как упоминал Питер Смит, алгоритм A * является распространенным для этой проблемы. Другие включают Дейкстры и Беллман-Форд .

Answer 2

Вы можете реализовать алгоритм A *. Из этого вы можете сначала построить график, а затем следовать псевдокоду на странице википедии.