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

Вы можете использовать алгоритм Флойда – Уоршалла. Вот псевдокод, предоставленный 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] );

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

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

Дано ограничение пути: A - B - A

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

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

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

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

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

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

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

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

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

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

С уважением, Ян

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

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 строки, но это запутает решение

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

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

Это решение не особенно эффективно, но явно полиномиально.