Difference between revisions of "TADM2E 6.19"
From Algorithm Wiki
(Created page with "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...") |
(6.19 alternative solution) |
||
| Line 2: | Line 2: | ||
After running the algorithm we need to search main diagonal for minimum amount, which is additional O(n). | After running the algorithm we need to search main diagonal for minimum amount, which is additional O(n). | ||
| + | |||
| + | ---- | ||
| + | === Alternative solution === | ||
| + | <pre> | ||
| + | 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) | ||
| + | </pre> | ||
| + | --[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 09:37, 23 July 2020 (UTC) | ||
Latest revision as of 09:37, 23 July 2020
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)
