Написать функцию поиска пути наименьшей стоимости.

Нужна готовая функция на C++, как указано ниже (переменные не обязательно писать кириллицей).

Платформа windows visual studio 2010.

Можно применять STL. Если вы используете какие то сторонние библиотеки для работы с графами, то обязательно предварительно сообщите об этом.

Если стоимость проекта занижена, то сообщите об этом.

1) Это сама матрица

// матрица клеток где ряд-столбец. Если значение клетки меньше или равно нулю, то клетка непроходима, если больше то проходима и какова стоимость прохода.

int ** matrix;

// пример инициализации

matrix[0][1]=0; // нет прохода

matrix[0][2]=1; // самая быстрая клетка

matrix[0][3]=5; // медленная клетка

...

2) Поиск должен вестись как по 4 так и 8 направлениям (должна быть возможность выбора либо только горизонтальный-вертикальный, либо еще и по диагонали).

3) обязательно сообщите имя алгоритма и предполагаемое время выполнения.

4) Вот объявление функции

// matrix_ уже инициализована.

// готовый_путь - сюда должен попасть путь. В pair соответственно первый элемент ряд , второй столбец.

template

bool find_path(index_ старт_ряд , index_ старт_столбец , index_ конец_ряд , index_ конец_столбец , index_ всего_рядов_карты , index_ всего_столбцов_карты ,index_ ** matrix_ , std::vector> & готовый_путь);

{}

То есть функция должна на основе известных, передаваемых параметров, рассчитать последний параметр.

5) (желательно но не обязательно) готовый_путь должен возвращать путь даже в случаи, если на указанную клетку попасть нельзя, вместо этого он возвращает путь до ближайщих к цели доступных клеток.

6) Если не совсем понятно, что требуется то обязательно сообщите.