Обмен технологиями

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

Оглавление

Алгоритм Флойда

определение

Применение

Меры предосторожности

Идеи решения проблем

Основные шаги

AcWing 343. Сортировка

Описание вопроса

запустить код

Идеи кода

Улучшайте идеи

Алгоритм Флойда

определение

Алгоритм Флойда, полное название алгоритма Флойда-Уоршалла, представляет собой алгоритм динамического программирования, используемый для решения задачи о кратчайшем пути между всеми парами вершин графа. Он подходит для взвешенных ориентированных графов и может обрабатывать ребра с отрицательным весом (но не графы, содержащие циклы с отрицательным весом), а также может определять, есть ли в графе циклы с отрицательным весом.

Применение

1. Вычислить кратчайший путь между всеми парами вершин: В таких областях, как анализ социальных сетей, планирование транспортных сетей, проектирование сетей связи и т. д., алгоритм Флойда является хорошим выбором, когда необходимо вычислить кратчайшее расстояние между любыми двумя точками.
2. Обнаружение циклов отрицательного веса: В некоторых сценариях применения необходимо следить за тем, чтобы на графике не было циклов отрицательного веса, поскольку это может указывать на некоторую аномалию или состояние ошибки в системе.

Меры предосторожности

• потребление памяти : Пространственная сложность алгоритма Флойда равна O(n^2), где n — количество вершин в графе. Для крупномасштабных графиков это может стать проблемой.
• временная сложность: временная сложность алгоритма Флойда равна O(n^3). Когда количество вершин велико, алгоритм может работать очень медленно.
• цикл с отрицательным весом : Если в графе имеется цикл с отрицательным весом, алгоритм Флойда попадет в бесконечный цикл, поскольку, начиная с узла, длина пути через этот цикл может уменьшаться бесконечно. В практических приложениях такие ситуации необходимо обнаруживать и обрабатывать в первую очередь.
• Алгоритмы могут обнаруживать циклы отрицательного веса:Если в ходе работы алгоритма обнаружено, что кратчайший путь от вершины до самой себя меньше 0, то есть D[i][i] < 0, то в графе имеется хотя бы один цикл с отрицательным весом, и в настоящее время алгоритм не может дать правильный результат кратчайшего пути.
• Для очень больших графов высокая временная и пространственная сложность алгоритма может стать узким местом. В настоящее время вам может потребоваться рассмотреть более эффективные алгоритмы или использовать более профессиональные структуры данных и методы оптимизации.

Идеи решения проблем

Основная идея алгоритма Флойда — динамическое программирование, а его основные этапы заключаются в следующем:

1. Инициализация: установите матрицу расстояний D в матрицу смежности графа, то есть D[i][j] = Weight(i, j for i != j), если (i, j) не связано, то Д[i][ j] = ∞; D[i][i] = 0.
2. Динамическое программирование: для k = от 1 до n обновите D так, чтобы D[i][j] = min(D[i][j], D[i][k] + D[k][j]), что Проверить, можно ли сократить расстояние от i до j через промежуточный узел k.
3. Результат: окончательная матрица D содержит кратчайшие длины путей между всеми парами вершин. Если существует определенный D[i][j] < 0 и i != j, а в процессе обновления возникает D[i][i] < 0, это означает, что в графе имеется цикл с отрицательным весом.

Реализация алгоритма Флойда обычно использует тройной цикл. Внешний цикл обходит все промежуточные вершины k, а два внутренних цикла обходят все пары вершин (i, j), чтобы проверить, существует ли более короткий путь.

Основные шаги

Предположим, у нас есть взвешенный граф G, содержащий n вершин, мы можем использовать двумерный массивdist[][] для хранения кратчайшей длины пути между каждой парой вершин. Изначально,dist[i][j]устанавливается как вес непосредственно связанного ребра в графе. Если между i и j нет непосредственно связанного ребра, то.dist[i][j]Установлено на бесконечность (означает недостижимость).

1. инициализация : Создайте матрицу D размера n×n, где D[i][j] инициализируется весом прямого ребра от i до j в графе или устанавливается равным бесконечности, если между i и j нет прямого ребра. Диагональный элемент D[i][i] = 0.

2. динамическое программирование : Для каждой вершины k (как промежуточной вершины) обновить кратчайший путь между каждой парой вершин i и j. Можно получить более короткий путь с k в качестве промежуточной точки. Формула обновления: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Это означает, что если путь от i до j становится короче через k в качестве промежуточной вершины, обновите D[i][j].

3. Вывод результата: После n раундов итераций каждый элемент D[i][j] в матрице D представляет собой кратчайший путь от i до j.

AcWing 343. Сортировка

Описание вопроса

343. Сортировка - Банк вопросов AcWing

запустить код

#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;
}

Идеи кода

1. инициализация: использоватьdistДвумерный массив инициализируется бесконечностью, а это означает, что по умолчанию между неравенствами нет определенного отношения порядка.
2. Чтение ввода: прочитать отношение из стандартного ввода в формате «B > A», указывая, что B лучше, чем A.
3. Обработка отношений:
   • При чтении новой связи проверяется, нет ли какого-либо противоречия (т. е. конфликтует ли ранее определенная связь с новой связью).
   • возобновлятьdistМатрица, использующая алгоритм Флойда для обновления кратчайшего пути между всеми неравенствами, фактически обновляет отношения «приоритета» или «порядка».
4. Проверьте надежность сортировки:
   • Убедитесь, что все неравенства связаны, т. е. каждая точка может достигать любой другой точки, а длина пути не бесконечна.
   • Если сортировка обнаружена в процессе чтения связи или сортировка все еще не может быть определена после прочтения всех связей, будет выведена соответствующая информация.

Улучшайте идеи

• Повышение эффективности : Текущий вызов Floyd выполняется сразу после добавления каждой новой связи, что может быть необязательно. Вы можете подождать, пока все связи будут прочитаны, прежде чем снова выполнять алгоритм Флойда, чтобы уменьшить количество ненужных вычислений.
• Упростите логику : Текущий код более сложен в обнаружении противоречий и определении логики завершения сортировки. Вы можете попытаться упростить логику, например, используя более интуитивные структуры данных или алгоритмические шаги для проверки этих условий.
• ясность кода: может повысить ясность комментариев и структуры кода, упрощая понимание и поддержку кода.