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)

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?


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.