.question | Shortest Path Problem

Пытаюсь наверстать все лекции по «конкретной математике», что когда-то сознательно были прогуляны на первом курсе в универе, а потому интересуют популярные решения одной, довольно банальной проблемы, завязанной вокруг теории графов.

Предположим, что есть у меня таблица с нодами, что-то из серии CREATE TABLE nodes(id INT4, name VARCHAR(255)), далее есть вторая таблица, в которой сохранены все «отношения» между любой пары нод, например: CREATE TABLE paths(parent INT4, child INT4).

Задача такова – найти самый короткий путь между любыми двумя нодами (например, между нодами 1 и 3 на рисунке). Какие есть алгоритмы, кроме тех, что описаны в википедии? Да и вообще, есть ли они?

Aug. 13, 2005 // 13:16 | Комментарии (16)