Какой алгоритм я могу использовать для поиска кратчайшего пути между указанными типами node в графе?

Ответ 1

Вы можете использовать алгоритм Флойда-Варшалла. Здесь псевдокод, указанный WikiPedia:

/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to 
   (infinity if there is none).
   Also assume that n is the number of vertices and edgeCost(i,i)=0
*/

int path[][];

/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
   from i to j using intermediate vertices (1..k-1).  Each path[i][j] is initialized to
   edgeCost(i,j) or infinity if there is no edge between i and j.
*/

procedure FloydWarshall ()
    for k: = 1 to n
        for each (i,j) in {1,..,n}2
            path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

Мне пришлось написать программу для курса алгоритмов по этой же проблеме. Этот алгоритм работал как прелесть! Гудлак.

Ответ 2

Существует много алгоритмов, которые будут лучше, чем вычисление всех возможных путей. Первый поиск по ширине является базовой отправной точкой для семейства алгоритмов, которые я имею в виду, Самый лучший поиск является подходящим, потому что у вас установлены определенные вершины, и если вы можете получить больше информации о своем проблемном пространстве, вы можете использовать A* или алгоритм Дейкстры. (В каждом случае поиск путей из набора допустимых начальных узлов.)

Повторите свое редактирование: ваше ограничение пути (массив типов node, который вам нужно удовлетворить) не мешает вам работать с этими алгоритмами; совершенно наоборот, это помогает им работать лучше. Вам просто нужно реализовать их таким образом, чтобы включить ограничение пути, ограничивая вершины, доступные на каждом шаге поиска, тем, которые являются действительными с учетом ограничения.

Ответ 3

Как сказал Ян, вам просто нужен обычный алгоритм кратчайшего пути (например, Dijkstra или алгоритм Floyd); однако вам необходимо преобразовать свой входной график, чтобы выходной путь соответствовал вашему ограничению пути.

Учитывая ограничение пути: A - B - A

Создайте новый график G и вставьте все вершины из A в G с новыми ярлыками типа a_01. Затем вставьте все вершины из B в G и соедините вершины A с вершинами B (ребра должны быть направлены к вновь вставленным узлам), копируя затраты из исходного графика. Затем вы повторите этот шаг с помощью A (и любых других компонентов пути), соединяющих вновь вставленные вершины с теми, что находятся в B. Таким образом, вы создаете граф, где только пути, которые существуют, удовлетворяют ограничению пути. Затем вы можете использовать обычные алгоритмы кратчайшего пути.

Ключевым понятием является то, что при повторном посещении класса вы фактически посещаете отдельный набор узлов и вам нужны только ребра, которые соединяют соседние классы узлов.

Ответ 4

Вот как я сейчас интерпретирую вашу проблему.

Красные стрелки меня вручную отслеживают пути, которые соответствуют заданному ограничению заказа.

Затраты не предоставляются, но предполагается, что все ссылки несут стоимость, а затраты на связь различны.

Если это точно описывает сценарий, который вы пытаетесь решить, скажите так, чтобы другие могли лучше ответить на вопрос.

Ответ 5

При пересмотре вашего вопроса кажется, что вы запрашиваете один node на букву - в этом случае это простое решение динамического программирования. Вычислите все кратчайшие пути длины 1, которые удовлетворяют началу вашей последовательности, между каждой пары узлов. Тогда для k всех таких путей для всех пар node тривиально построить для k + 1.

Ответ 6

Вот псевдокод с динамическим программным решением:

n - length of desired path
m - number of vertices
types[n] // desired type of ith node
vertice_types[m]
d[n][m] // our DP tab initially filled with infinities

d[0][0..m] = 0
for length from 1 to n 
  for b from 0 to m
    if types[length] == vertice_types[b]
      for a from 0 to m
        if types[length-1] == vertice_types[a]
          d[length][b] = min(d[length][b], d[length-1][a] + cost(a,b))

ваш путь минимальной стоимости - min (d [n] [0..m])

вы можете уменьшить размер таблицы d до 2 строк, но это будет запутывать решение

Ответ 7

Насколько я понимаю ваш вопрос, вам нужен кратчайший путь в ориентированном графе. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm должен дать вам идею.

Ян

Ответ 8

• Вычислить все пары кратчайших путей в каждом блоке эквивалентности.
• Теперь создадим граф, у которого нет никаких межклассовых ребер, но грани которого между классами соответствуют кратчайшему пути в этом классе, что приводит к определенному node другого класса.

Надеюсь, что это ясно.

Это решение не особенно эффективно, но явно многочлено.