Find cycle of shortest length in a directed graph with positive weights

user_374499 0
Viewed 45995

I was asked this question in an interview, but I couldn't come up with any decent solution. So, I told them the naive approach of finding all the cycles then picking the cycle with the least length.

I'm curious to know what is an efficient solution to this problem.

dijkstra graph algorithm
5 Answers

Below is a simple modification of Floyd - Warshell algorithm.

V = 4
INF = 999999



def minimumCycleLength(graph): 
    dist =  [[0]*V for i in range(V)]
    for i in range(V):
            for j in range(V):
                dist[i][j] = graph[i][j];
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j] ,dist[i][k]+ dist[k][j])
    length = INF
    for i in range(V):
        for j in range(V):
            length = min(length,dist[i][j]) 
    return length


graph = [ [INF, 1, 1,INF],
        [INF, INF, 1,INF],
        [1, INF, INF, 1],
        [INF, INF, INF, 1] ]
length = minimumCycleLength(graph)
print length
user_81327900
Related