Кратчайший путь от одной точки до другой.

[firephenix]

Подскажите пожалуйста идею или названия алгоритма для нахождения кратчайшего пути от одной точки до другой. Алгоритм Дейксты в данной задаче использовать нельзя из-за того что в задаче нужно как можно меньше использовать оперативную память, даже в ущерб времени выполнения. (всего вершин не больше 10.000, так что двумерный массив с таким количеством ячеек" 10.000*10.000 " для хранения длины ребра, будет использовать слишком много памяти).

[mMAg]

Алгоритм Дейкстры без вариантов. Он не зависит от того, как вы там граф храните. И в отличие, например, от алгоритма Флойда ему матрица длин ребер не нужна. Вы спокойно можете хранить свои ребра в списке, например, или в куче, или вообще где и как угодно, если там у вас граф разреженный, а вершин много.
А если он у вас не разреженный, тогда сообщите, пожалуйста, как вы собираетесь хранить примерно 10.000 * 10.000 значений не занимая такого количества ячеек памяти?

[sfok3]

а может алгоритм поиска пути A* ?
Теорию, картинки и код можно посмотреть ТУТ

[mMAg]

Сообщение от sfok3

а может алгоритм поиска пути A* ?
Теорию, картинки и код можно посмотреть ТУТ

Боюсь вас огорчить, но это и есть Дейкстра на списках, если в качестве оценки принимать всегда ближайшую вершину.
Вообще-то у вас была проблема с памятью, насколько я понимаю. Для того чтобы она отпала, нужно хранить ребра, а не таблицу смежностей. А алгоритм какой выбирать, это уже дело третье.