2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Sisällysluettelo
Floydin algoritmi, Floyd-Warshall-algoritmin koko nimi, on dynaaminen ohjelmointialgoritmi, jota käytetään ratkaisemaan lyhimmän polun ongelma graafin kaikkien pisteparien välillä. Se sopii painotetuille suunnatuille kaavioille ja pystyy käsittelemään negatiivisen painotuksen reunoja (mutta ei negatiivisia painosyklejä sisältäviä kaavioita) ja voi havaita, onko kaaviossa negatiivisia painosyklejä.
Floydin algoritmin ydinajatus on dynaaminen ohjelmointi, ja sen perusvaiheet ovat seuraavat:
Floydin algoritmin toteutuksessa käytetään yleensä kolmoissilmukkaa. Ulompi silmukka kulkee kaikkien välipisteiden k läpi ja kaksi sisäsilmukkaa kaikkien kärkiparien (i, j) läpi tarkistaakseen, onko olemassa lyhyempi polku.
Oletetaan, että meillä on painotettu graafi G, joka sisältää n kärkeä, voimme käyttää kaksiulotteista taulukkoadist[][]
tallentaaksesi lyhimmän polun pituuden kunkin kärkiparin välille. Aluksidist[i][j]
on asetettu graafin suoraan yhdistetyn reunan painoon. Jos i:n ja j:n välillä ei ole suoraan kytkettyä reunaa, niindist[i][j]
Aseta äärettömään (ilmaisee tavoittamatonta).
alustus : Luo n×n matriisi D, jossa D[i][j] alustetaan graafin i:n ja j:n suoran reunan painoon tai asetetaan äärettömyyteen, jos i:n ja j:n välillä ei ole suoraa reunaa. Diagonaalielementti D[i][i] = 0.
dynaaminen ohjelmointi : Päivitä jokaiselle kärkipisteelle k (välipisteenä) lyhin polku kunkin kärkiparin i ja j välillä. On mahdollista saada lyhyempi polku k välipisteenä. Päivityskaava on: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Tämä tarkoittaa, että jos polku i:stä j:hen lyhenee k:n kautta välipisteenä, päivitä D[i][j].
Tulostulostus: n iteraatiokierroksen jälkeen jokainen matriisin D elementti D[i][j] on lyhin polun pituus i:stä j:hen.
343. Lajittelu - AcWingin kysymyspankki
- #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;
- }
dist
Kaksiulotteinen taulukko alustetaan äärettömyyteen, mikä tarkoittaa, että epäyhtälöiden välillä ei ole oletusarvoisesti määrättyä järjestyssuhdetta.dist
Matrix, joka käyttää Floydin algoritmia päivittääkseen lyhimmän polun kaikkien epätasa-arvojen välillä, tässä itse asiassa päivittää "prioriteetti" tai "järjestys" -suhdetta.