2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
सामग्रीसूची
फ्लोयड्-वार्शल् एल्गोरिदम् इत्यस्य पूर्णं नाम फ्लोयड्-एल्गोरिदम् इति गतिशीलप्रोग्रामिंग-एल्गोरिदम् अस्ति यस्य उपयोगः आलेखे सर्वेषां शिखरयुग्मानां मध्ये लघुतममार्गसमस्यायाः समाधानार्थं भवति इदं भारितनिर्देशितलेखानां कृते उपयुक्तं भवति तथा च ऋणात्मकभारधाराः (किन्तु ऋणात्मकभारचक्रयुक्तानि आलेखाः न) सम्भालितुं शक्नोति, तथा च आलेखे ऋणात्मकभारचक्राणि सन्ति वा इति ज्ञातुं शक्नोति
फ्लोयड् इत्यस्य एल्गोरिदम् इत्यस्य मूलविचारः गतिशीलप्रोग्रामिंग् अस्ति, तस्य मूलभूतपदार्थाः च निम्नलिखितरूपेण सन्ति ।
फ्लोयड् इत्यस्य एल्गोरिदम् इत्यस्य कार्यान्वयनम् सामान्यतया त्रिगुणितपाशस्य उपयोगं करोति बाह्यपाशः सर्वान् मध्यवर्तीशिखरान् k भ्रमति, अन्तः पाशद्वयं च सर्वान् शिखरयुग्मान् (i, j) भ्रमति यत् लघुतरः मार्गः अस्ति वा इति
मानातु यत् अस्माकं कृते n शिखरयुक्तः भारितः आलेखः G अस्ति, वयं द्विविमीयसरण्याः उपयोगं कर्तुं शक्नुमःdist[][]
प्रत्येकस्य शिखरयुग्मस्य मध्ये लघुतममार्गदीर्घतां संग्रहीतुं । प्रारम्भे २.dist[i][j]
आलेखे प्रत्यक्षतया सम्बद्धस्य धारस्य भारं प्रति सेट् भवति यदि i तथा j मध्ये प्रत्यक्षतया सम्बद्धः धारः नास्ति तर्हिdist[i][j]
अनन्तं (अप्राप्यं सूचयति) इति सेट् कुर्वन्तु ।
आरम्भीकरणम् : एकं n×n आकृतिं D रचयन्तु, यत्र D[i][j] आलेखे i तः j पर्यन्तं प्रत्यक्षधारस्य भारस्य आरम्भः भवति, अथवा यदि i तथा j मध्ये प्रत्यक्षधारः नास्ति तर्हि अनन्तं प्रति सेट् भवति तिर्यक् तत्व D[i][i] = 0.
गतिशील प्रोग्रामिंग : प्रत्येकस्य शिखरस्य k (मध्यवर्ती शिखरस्य रूपेण), प्रत्येकस्य शिखरयुग्मस्य i तथा j मध्ये लघुतमं मार्गं अद्यतनं कुर्वन्तु k इत्यनेन सह मध्यबिन्दुरूपेण लघुतरं मार्गं प्राप्तुं शक्यते । अद्यतनसूत्रं अस्ति : D[i][j] = min(D[i][j], D[i][k] + D[k][j]) । अस्य अर्थः अस्ति यत् यदि i तः j पर्यन्तं मार्गः k मार्गेण मध्यवर्ती शिखररूपेण लघुः भवति तर्हि D[i][j] अद्यतनं कुर्वन्तु ।
परिणामनिर्गमः: पुनरावृत्तीनां n गोलानां अनन्तरं D[i][j] इति प्रत्येकं तत्त्वं i तः j पर्यन्तं लघुतमं मार्गदीर्घता भवति ।
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;
- }
dist
द्विविधा सरणी अनन्ततां यावत् आरभ्यते, यस्य अर्थः अस्ति यत् पूर्वनिर्धारितरूपेण असमानतानां मध्ये निश्चितः क्रमसम्बन्धः नास्ति ।dist
Matrix, सर्वेषां असमानतानां मध्ये लघुतममार्गं अद्यतनीकर्तुं Floyd इत्यस्य एल्गोरिदम् इत्यस्य उपयोगेन, अत्र वस्तुतः "प्राथमिकता" अथवा "क्रमण" सम्बन्धं अद्यतनं करोति ।