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

Question

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

Answer 1

Пусть admat будет матрицей смежности для вашего графа. Тогда

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

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

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

определить образец еще?

Answer 2

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

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

Answer 3

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

Пусть 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 содержит C (B, 2), C (E, 2), C (D, 2). Отсюда и в сочетании с исследованным списком вы можете проследить до исходного узла. Например, C(B, 2) B(A, 1) A(None, 0).

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

Answer 4

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

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

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

тогда пусть w будет узлом в L (j-1), а v находится в L (j).

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

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

Answer 5

Алгоритм Дейкстры используется для поиска кратчайших путей.

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