Предложения для KSPA на неориентированном графе
Ну, если Вы хотите "начать с нуля уровня", я рекомендую изучить блок. да блок. Я учился 6502, можно изучить x86, если Вам нравится или рука или миллион операций в секунду. Найдите эмулятор или прерыватель и прочитайте некоторые учебные руководства. Вы поймете точно, как ЦП, работы и код будут иметь намного больше смысла (как то, почему getkeys не обновляет, пока Вы не делаете pollkeys и и т.д.).
После этого я рекомендую C#, потому что это не столь противно как c/c ++ (я, прежде всего, использую C++). Вы поймете, как строка C# могла быть представлена в блоке. C# позволяет Вам делать больше вещей, которые Вы хотите сделать в отличие от c, и C++ (нанимает список вещей, которые мы можем сделать в C++, который мы сможем сделать в следующем стандарте http://en.wikipedia.org/wiki/C%2B%2B0x , C# имеет несколько из них).
, Если Вы хотите изучить много, можно попытаться учить язык, который я рекомендую здесь https://stackoverflow.com/questions/498964/the-difficulty-in-learning-new-languages-by-yourself/578618#578618, который я думаю, хорошая идея после блока.
1 ответ
Сложность времени: O (K * (E * log (K) + V * log (V)))
Сложность памяти O (K * V) (+ O (E ) для хранения входных данных).
Мы выполняем модифицированную Джикстру следующим образом:
- Для каждого узла вместо сохранения наилучшей известной на данный момент стоимости маршрута от начального узла. Мы сохраняем лучшие K маршрутов от начального узла
- . При обновлении соседей узлов мы не проверяем, улучшает ли он лучший в настоящее время известный путь (как это делает Djikstra), мы проверяем, улучшает ли он худший из K 'лучших известный в настоящее время путь.
- После того, как мы уже обработали первый из K лучших маршрутов узла, нам не нужно находить K лучших маршрутов, а остается только K-1, а после еще один K-2. Это то, что я назвал K '.
- Для каждого узла мы будем держать две очереди приоритетов для K' наиболее известных на данный момент длин путей.
- В одной приоритетной очереди кратчайший путь находится сверху. Мы используем эту приоритетную очередь, чтобы определить, какая из K 'является лучшей и будет использоваться в обычных приоритетных очередях Djikstra в качестве представителя узла.
- В другой приоритетной очереди самый длинный путь находится наверху. Мы используем его для сравнения возможных путей с худшим из путей K.