TADM2E 6.19

Simple application of Floyd-Warshall algorithm for directed graphs O(n^3).

After running the algorithm we need to search main diagonal for minimum amount, which is additional O(n).

---

Alternative solution

1. Traverse all the vertices of the graph and check if they have edges pointing to themselves, if so, return the weight of the minimal loop  # O(n*m)
2. Use the Floyd-Warshall algorithm to find the shortest distances between any two vertices of the graph  # O(n^3) 
3. Traversing the distance table obtained in the previous step, return the minimum value of D[i][j] + D[j][i]  # O(n^2)

--Bkarpov96 (talk) 09:37, 23 July 2020 (UTC)