TADM2E 6.19

From Algorithm Wiki
Revision as of 09:37, 23 July 2020 by Bkarpov96 (talk | contribs) (6.19 alternative solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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)