В матрице значений найти маршрут с минимальным кол-вом значений.

[Boolean_Type]

Здравствуйте!
Есть задача: "Дана квадратная матрица 10х10, в которой указана стоимость проезда из города А в город В.
Найти маршрут, реализующий проезд из города в город за минимальную стоимость (реализовать задачу на HTML + javascript)".

Сначала думал обойти скриптом все возможные пути. Но понял, что это не оптимально, т.к. матрица может быть и больше. Скрипту в любом случае понадобится много времени, чтобы обойти все ходы, а это не норм. Нужен алгоритм.
Поискав задачи о маршрутизации, набрёл на теорию графов - а именно: алгоритм Дейкстры и иже с ним (хотя непонятно, что будет служить рёбрами графа), а также некий-то поток минимальной стоимости.
Дело в том, что я ни хрена не соображаю в этом. Отсюда вопрос: возможно ли это решить без применения дискретной математики? Может, кто сталкивался?

[Brutus]

Без математики только рекурсией, а это не самое оптимальное решение.

Используй алгоритм левита, благо инфы о нем на русском полно.

Для начала вот: https://ru.wikipedia.org/wiki/Алгоритм_Левита

[Boolean_Type]

Спасибо, но статьи из Вики об, опять же, графах, а также код на С# или С++ мне вряд ли поможет.
Я уже сталкивался с этой статьёй.

[Boolean_Type]

Попробовал следующим образом (исходный код можно увидеть здесь, я лишь добавил числа, которые будут "стоимостями" клеток; в исходном коде стоимость (cost, g-параметр) изначально равна 1). Ссылки на песочницы:
JS Bin
или codepen, код в них один и тот же, так что любая подойдёт для просмотра.

Таблица кликабельна, в ней ищется, как я писал, выше, кратчайший путь. Но вы можете заметить, что алгоритм отчего-то работает неверно. Может, у кого будут идеи?

[nerv_]

http://www.policyalmanac.org/games/a...torial_rus.htm
http://qiao.github.io/PathFinding.js/visual/

[Boolean_Type]

Спасибо Вам большое, но неужто Вы думаете, что я этого не видел?) Ещё как видел и читал)

В моём посте выше уже есть готовый код. У меня не было достаточно времени написать подобное самому с нуля, т.к. эта задача всё-таки не из простых. Но я попытался адаптировать код в ссылках выше под свою задачу, однако возникла проблема. Я уверен, что почти достиг цели, просто упорно не могу понять, где же я не так передаю данные (или вообще не передаю). По-моему, там проблема со стоимостью у соседей тек. элемента (но как её кодер устанавливал - хрен его знает).
Надеюсь, Вы или кто-либо другой подскажет, что не так в коде (я видел, тут такие волшебники бывают :-)) ).
А кидать ссылки на теорию лучше не нужно - я уже практически всё обшерстил, серьёзно)

[рони]

Boolean_Type,
по ссылкам такое впечатление - что предыдущий найденный маршрут мешает поиску нового маршрута

[Boolean_Type]

рони, я ещё заметил при выводе в консоли значений соседей, что правильно устанавливаются только 2 из них - первые, а остальные почему-то 1.
Есть там метод Vertex:

PathFinding.Vertex = function(dest, cost) {
  
    this.cost = cost || 1;
    this.dest = dest;
    
};

..., явно в случаях двух последних (или одного - если квадрат к стенке прилегает) соседей cost не передаётся методу, т.е. устанавливается равным 1.