0
$\begingroup$

The following slow algorithm (implemented from CLRS book) which runs in $\Theta(V^4)$ works fine for computing shortest paths distances:

def extendShortestPath(L, PI, W):
    n = len(L)
    Lprime = [[float('inf') for x in range(n)] for y in range(n)]
    PIprime = [[-1 for x in range(n)] for y in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if (Lprime[i][j] > L[i][k] + W[k][j]):
                    Lprime[i][j] = L[i][k] + W[k][j]
                    PIprime[i][j] = k        # does not work!
                    PIprime[i][k] = PI[i][k] # does not work!
    return Lprime, PIprime

def slowAllPairsShortestPaths(W):
    n = len(W)
    L = W
    PI = [[-1 for x in range(n)] for y in range(n)]
    for m in range(1, n):
        L, PI = extendShortestPath(L, PI, W)
    return L, PI

if __name__ == '__main__':
    W = [[float('inf') if x != y else 0 for x in range(5)] for y in range(5)]
    W[0][1] = 3
    W[0][2] = 8
    W[0][4] = -4
    W[1][3] = 1
    W[1][4] = 7
    W[2][1] = 4
    W[3][0] = 2
    W[3][2] = -5
    W[4][3] = 6
    L, PI = slowAllPairsShortestPaths(W)
    print(L)
    print(PI)

enter image description here enter image description here

But besides computing shortest paths distances, I also need to determine the predecessor vertex of every vertex in the graph for every source vertex. I understand that the relaxing step determines the predecessor. So I added the commented lines to extendShortestPath but it doesn't seem to work. How can I compute the predecessor subgraph?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.