Временная сложность алгоритма кратчайшего пути - PullRequest
Новая
       45

Временная сложность алгоритма кратчайшего пути

0 голосов
/ 02 октября 2018

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

shortestPaths(undirected graph G, startNode v, endNode end)
    initialize  all levels of nodes to -1
    count = 1;
    initialize queue Q = {v}
    level(v) = 0

    while Q is not empty
        curr = pop(Q)

        if( curr == end)
            w = pop(Q)
            while(level(w)==level(curr))
                if(w == end)
                    count++
                w=pop(Q)
            return count

        for all neighbors (nxt) of node curr do 
            if( level(nxt) == -1 )
                level(nxt) = level(curr) + 1
                Push(Q, nxt)
            else if( level(nxt) == level(curr) + 1 )
                Push(Q, nxt)
            else if( level(nxt) > level(curr) + 1)
                Level(nxt) = Level(curr) + 1
    return count

1 Ответ

0 голосов
/ 02 октября 2018

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

Попробуйте что-то вроде этого: 

initialize  all counts of nodes to 0                     // added
counts(v) = 1                                            // added
...
while Q is not empty
    curr = pop(Q)

    if( curr == end)
        return counts(curr)

    for all neighbors (nxt) of node curr do 
        if( level(nxt) == -1 )
            level(nxt) = level(curr) + 1
            counts(nxt) = counts(curr)                   // added
            Push(Q, nxt)
        else if( level(nxt) == level(curr) + 1 )
            counts(nxt) += counts(curr)                  // added & removed
return 0

И это имеет ту же сложность, что и BFS - O(|E|+|V|).

...