|
В матрице значений найти маршрут с минимальным кол-вом значений.
Здравствуйте!
Есть задача: "Дана квадратная матрица 10х10, в которой указана стоимость проезда из города А в город В.
Найти маршрут, реализующий проезд из города в город за минимальную стоимость (реализовать задачу на HTML + javascript)".
Сначала думал обойти скриптом все возможные пути. Но понял, что это не оптимально, т.к. матрица может быть и больше. Скрипту в любом случае понадобится много времени, чтобы обойти все ходы, а это не норм. Нужен алгоритм.
Поискав задачи о маршрутизации, набрёл на теорию графов - а именно: алгоритм Дейкстры и иже с ним (хотя непонятно, что будет служить рёбрами графа), а также некий-то поток минимальной стоимости.
Дело в том, что я ни хрена не соображаю в этом. Отсюда вопрос: возможно ли это решить без применения дискретной математики? Может, кто сталкивался?
|