Алгоритм Dijkstra для 2D массива в Java

Question

Алгоритм Dijkstra для 2D массива в Java

Вы можете найти полезную Стенд для тестирования объектов. Это не очень хорошо известно, но позволяет создавать экземпляры классов, выполнять статические методы и так далее. Это может быть полезно для обнаружения того, как использовать незнакомые API, или для быстрой отладки ваших собственных классов и методов, сохраняя создание тестового жгута для простых проверок.

Документацию по MSDN можно найти здесь:

http://msdn.microsoft.com/en-us/library/c3775d98%28VS.80%29.aspx

7

java algorithm multidimensional-array dijkstra

задан Bill the Lizard 19 September 2012 в 12:34

2 ответа

Другие вопросы по тегам:

java algorithm multidimensional-array dijkstra

Похожие вопросы:

score 9 · Answer 1

Представление, которое вы вызываете 2D-массивом, является матричным представлением графа, и проблема, которую вы пытаетесь решить, является экземпляром проблемы «Кратчайшие пути с одним источником». Алгоритм Дейкстры предназначен для решения этого типа проблем. Это может быть полезно http://renaud.waldura.com/doc/java/dijkstra/ . Скачайте код с сайта и прочтите документацию. В основном вам нужно будет написать код, подобный следующему

    RoutesMap map = map =  new DenseRoutesMap(5);
    map.addDirectRoute(City.A, City.B, 2);
    map.addDirectRoute(City.A, City.C, 3);
    map.addDirectRoute(City.B, City.A, 2);
    map.addDirectRoute(City.B, City.D, 5);
    map.addDirectRoute(City.B, City.D, 2);
    ...
    DijkstraEngine engine = new DijkstraEngine(map);
    int distance = engine.getShortestDistance(City.F);

score 0 · Answer 2

Не знаю, интересует ли еще кого-нибудь это матричное представление Диджикстры, но я думал о кодировании Диджикстры в ActionScript, и поэтому сначала мне пришлось научиться тому, как работает Диджикстра. Сделав это и пытаясь закодировать, я только вчера вечером понял, что могу представить узлы и расстояния в матрице, такой как у вас в верхней части этого поста.Моя теория состоит в том, что найти кратчайший путь будет очень просто. Я все еще экспериментирую, чтобы убедиться, что я исправлюсь.

В матрице;

a b c d e z а - 2 3 - - - б 2 - - 5 2 - в 3 - - - 5 - г - 5 - - 1 2 д - 2 5 1 - 4 z - - - 2 4 -

Я начинаю смотреть на строку «a» (поскольку это начальная точка) и выбираю наименьшее число в строке, равное 2 (под b). Поэтому я записываю путь как «a - b» со стоимостью 2. Затем я перехожу к строке b и снова нахожу наименьшее число СПРАВА от b (так как мы уже находимся в узле b. Это дает мне 2 под Таким образом, теперь путь равен «a - b - e» при общей стоимости 4. i Затем посмотрите на строку «e», и правило должно найти наименьшее число, которое появляется после столбца «e». Это дало бы мне «z» и полный путь как «a - b - e - z» и общую стоимость 8. Однако, помните, я понял это только вчера вечером, методология должна признать это, глядя на Строка «e» другая возможность - перейти к столбцу d по цене 1. Затем посмотрите на строку d, чтобы найти наименьшее число после строки d, что даст мне строку «z» по цене 2.

Следовательно, это лучшее решение с путем «a - b - e - d -z» с общей стоимостью 7, как вы правильно сказали.

Хорошо, мне все еще нужно закодировать это в ActionScript, но я интуитивно чувствую в том, что его будет очень легко закодировать в ActionScript. Боюсь, у меня нет никаких ожиданий. rince на Java, но если вы согласны с моим методом, код на Java должен быть легким.

Пол