число кратчайших путей между двумя вершинами графа

Question

1) У кого-нибудь есть идея получить число кратчайших путей в неориентированном невзвешенном графе? Я хочу заполнить 2-мерную матрицу, которая имеет число кратчайших путей для любой вершины i, j, 2) другой вопрос заключается в том, как получить число кратчайших путей между двумя вершинами i, j таким образом, что путь должен пройти определенной вершины. Спасибо заранее.

Answer 1

Dijkstra's algorithm предназначенный для поиска самых коротких путей.

NB Первое Google находит, если вы попытаетесь использовать его с shortest path algorithm поиск ...

Answer 2

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Дейкстра является вашим другом. Чтобы найти кратчайший путь, включающий конкретный узел, примените Dijkstra для получения кратчайшего пути от A до B, а затем от B до C. Там это ...

Чтобы получить количество путей, разделяющих одну и ту же стоимость, это должно быть легко изменить Dijkstra для этого, чтобы оставить что-то для вашей домашней работы ... :)

Answer 3

Вы можете использовать BFS для этой ситуации. Вот алгоритм, который я только что сделал из своей памяти о некоторых курсах AI пару лет назад. Я не могу убедиться, что он работает безупречно, но, надеюсь, он даст вам несколько советов.

Давить X(p, d) обозначить узел X, родитель которого p, а расстояние от его родителя - d.

function findAllShortestPaths(...): 

RET = set() 
queue = [S(None, 0)] 
explored = set() 
while queue is not empty: 
    Node = queue.dequeue() 

    if Node is the one we're searching for: 
     if Node is not in RET: 
      RET.add(Node) 
     else: 
      if Node.d <= d of the node in RET: 
       RET.add(Node) 
     continue 

    if Node is not in explored: 
     explored.add(Node) 
    else: 
     if Node.d <= d of the node in explored: 
      explored.add(Node) 
     else: 
      continue 

    for Child in Node.childrens: 
     if Child is not in explored: 
      queue.append(Child(Node, Node.d + 1)) 

    return RET, explored 

Вот пример. Предположим, что у вас есть 5-точечный (A, B, C, D, E) график, строки которого связаны следующим образом; AB, BC, CD, DA, EA, EB, EC, ED. Вы хотите найти все кратчайшие пути от А до С.

Пусть X(parent, distance) ---> Y(...) Z(...) означает, что X добавлен в исследуемый набор, Y и Z - это дети X, и они добавляются в очередь.

A(None, 0) ---> B(A, 1) E(A, 1) D(A, 1) 
B(A, 1) ---> E(B, 2) C(B, 2) 
E(A, 1) ---> C(E, 2) D(E, 2) 
D(A, 1) ---> C(D, 2) 

[E(B, 2) already in the explored list and the distance is 2 > E(A, 1), continue.] 

C(B, 2) ---> Our GOAL, add to RET 
C(E, 2) ---> Our GOAL, C already in RET but distance is equal, add to RET 

[D(E, 2) already in the explored list and the distance is 2 > D(A, 1), continue.] 

C(D, 2) ---> Our GOAL, C already in RET but distance is equal, add to RET 

Наконец, RET содержит С (В, 2), С (Е, 2), C (D, 2). Отсюда и в сочетании с разведанным списком можно вернуться к исходному узлу. Например, C(B, 2) B(A, 1) A(None, 0).

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

Answer 4

Пусть admat - матрица смежности для вашего графика. Затем

admat дает длину 1 путь между вершинами;

admat^2 дает длину 2 пути между вершинами;

admat^3 дает длину 3 пути между вершинами;

spot pattern еще?

Answer 5

Использование BFS позволяет свести к минимуму сложность.

Используйте BFS, и нам нужно сохранить дополнительный счетчик, чтобы Sum (w) в каждом слое.

let s - начальная вершина, и нам нужно найти нет кратчайшего пути к v.

то пусть w - узел в L (j-1), а v - в L (j).

тогда S (v) = суммирование {S (w)} + 1;

и S (v) обозначает не по кратчайшему пути между х и v.