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

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

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

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

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

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

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

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

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