Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Table of contents

Floyd Algorithm

definition

Application

Precautions

Problem Solving

The basic steps

AcWing 343. Sorting

Title Description

Run the code

Code ideas

Improvement ideas

Floyd Algorithm

definition

The Floyd algorithm, also known as the Floyd-Warshall algorithm, is a dynamic programming algorithm used to solve the shortest path problem between all pairs of vertices in a graph. It is applicable to weighted directed graphs, can handle negative weight edges (but cannot handle graphs with negative weight cycles), and can detect whether there are negative weight cycles in the graph.

Application

1. Compute the shortest path between all pairs of vertices：In fields such as social network analysis, transportation network planning, and communication network design, when it is necessary to calculate the shortest distance between any two points, the Floyd algorithm is a good choice.
2. Detecting Negative Weight Cycles: In some application scenarios, it is necessary to ensure that there are no negative weight cycles in the graph, as this may indicate some abnormal or error state in the system.

Precautions

• Memory consumption: The space complexity of Floyd's algorithm is O(n^2), where n is the number of vertices in the graph. For large graphs, this can become a problem.
• time complexity: The time complexity of Floyd's algorithm is O(n^3), and when the number of vertices is large, the algorithm may become very slow.
• Negative Weight Cycle：If there is a negative weight cycle in the graph, Floyd's algorithm will fall into an infinite loop, because starting from a node, the path length can be reduced infinitely through this cycle. In practical applications, such situations need to be detected and handled first.
• The algorithm can detect negative weight cycles:If during the execution of the algorithm it is found that the shortest path from a vertex to itself is less than 0, that is, D[i][i] < 0, then there is at least one negative weight cycle in the graph, and the algorithm cannot give the correct shortest path result.
• For very large graphs, the high time and space complexity of the algorithm may become a bottleneck. At this time, you may need to consider more efficient algorithms or use more specialized data structures and optimization techniques.

Problem Solving

The core idea of ​​Floyd's algorithm is dynamic programming, and its basic steps are as follows:

1. Initialization: Set the distance matrix D to the adjacency matrix of the graph, that is, D[i][j] = weight(i, j); for i != j, if (i, j) is not connected, then D[i][j] = ∞; D[i][i] = 0.
2. Dynamic programming: For k = 1 to n, update D so that D[i][j] = min(D[i][j], D[i][k] + D[k][j]), that is, check whether the distance from i to j can be shortened through the intermediate node k.
3. Result: The final D matrix contains the shortest path lengths between all vertex pairs. If there is a D[i][j] < 0 and i != j, and D[i][i] < 0 occurs during the update process, it means that there is a negative weight cycle in the graph.

Implementations of Floyd's algorithm usually use a triple loop, where the outer loop traverses all intermediate vertices k, and the inner two loops traverse all vertex pairs (i, j) to check whether there is a shorter path.

The basic steps

Suppose we have a weighted graph G with n vertices, we can use a two-dimensional arraydist[][]To store the shortest path length between each pair of vertices. Initially,dist[i][j]is set to the weight of the directly connected edge in the graph. If there is no directly connected edge between i and j, thendist[i][j]Set to infinity (indicating unreachable).

1. initialization: Create an n×n matrix D, where D[i][j] is initialized to the weight of the direct edge from i to j in the graph, or to infinity if there is no direct edge between i and j. The diagonal elements D[i][i] = 0.

2. Dynamic Programming: For each vertex k (as an intermediate vertex), update the shortest path between each pair of vertices i and j, and use k as the intermediate point to obtain a shorter path. The update formula is: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). This means that if the path from i to j becomes shorter by using k as the intermediate vertex, update D[i][j].

3. Result Output: After n rounds of iterations, each element D[i][j] in the matrix D is the length of the shortest path from i to j.

AcWing 343. Sorting

Title Description

343. Sorting - AcWing Question Bank

Run the code

#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
#define PII pair<int, int>
#define fi first
#define se second
#define endl 'n'
map<int, int> mp;
 
const int N = 210, mod = 1e9 + 7;
int T, n, m, k;
int a[N], dist[N][N];
PII ans[N];
 
void floyd(int x) // 以 x 为中转点，更新其他点。
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
}
 
bool pd() // 判断是否所有点都已确定
{
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++)
            if (dist[i][j] != 1e9)
                cnt++; // 当前点能到达的点数
        ans[i] = {cnt, i};
        for (int j = 1; j <= n; j++)
            if (i != j && dist[j][i] != 1e9)
                cnt++; // 能到达当前点的点数
        if (cnt != n)
            return 0;
    }
    sort(ans + 1, ans + n + 1);
    return 1;
}
 
int main() {
    while (cin >> n >> m && n) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j)
                    dist[i][j] = 1e9;
 
        int flag = 0;
        for (int i = 1; i <= m; i++) {
            char a, t, b;
            cin >> a >> t >> b;
            int x = a - 'A' + 1, y = b - 'A' + 1; // 现在要加一条从 y 到 x 的边
 
            if (!flag && dist[x][y] != 1e9) // 发现已经从x能到y，出现矛盾
            {
                printf("Inconsistency found after %d relations.n", i);
                flag = 1;
            }
 
            dist[y][x] = 1;
            floyd(x), floyd(y); // 分别以 x 和 y 为中转点更新其他点
            if (!flag && pd()) { // 发现所有点都已确定
                printf("Sorted sequence determined after %d relations: ", i);
                for (int i = 1; i <= n; i++)
                    cout << char(ans[i].se + 'A' - 1);
                printf(".n");
                flag = 1;
            }
        }
        if (!flag)
            printf("Sorted sequence cannot be determined.n"); // 无法确定
    }
 
    return 0;
}

Code ideas

1. initialization: Use onedistThe two-dimensional array is initialized to infinity, indicating that there is no definite order relationship between inequalities by default.
2. Reading Input: Read relations from standard input in the format of "B > A", indicating that B is superior to A.
3. Relationship Management:
   • When a new relationship is read, check whether there is any contradiction (i.e., the previously determined relationship conflicts with the new relationship).
   • renewdistMatrix, use Floyd's algorithm to update the shortest paths between all inequalities, which actually updates the "priority" or "sort" relationship.
4. Checking sorting determinism:
   • Check that all the relationships between inequalities are determined, that is, every point can reach every other point, and the path length is not infinite.
   • If the order is determined during the process of reading the relations, or if the order cannot be determined after reading all relations, output the corresponding information.

Improvement ideas

• Improved efficiency: Currently, the Floyd call is made immediately after each new relationship is added, which may not be necessary. You can wait until all relationships have been read before performing the Floyd algorithm again to reduce unnecessary calculations.
• Simplify the logic: The current code has complex logic for detecting inconsistencies and determining that the sort is complete. You can try to simplify the logic, such as using more intuitive data structures or algorithmic steps to check these conditions.
• Code Clarity: It can increase the clarity of comments and code structure, making the code easier to understand and maintain.