آموزش:الگوریتم:الگوریتم دایکسترا [المپدیـا]

فهرست مندرجات

الگوریتم دایکسترا راه‌کاری به منظور پیدا کم‌وزن مسیر از رأس مشخص آغاز بـه بقیـه رئوس درون گراف جهت‌دار و وزن‌دار (با وزن‌های مثبت) مـی‌دهد. الگوریتم وزن وزن یک مسیر درون گراف وزن‌دار برابر مجموع وزن یـال‌های آن است. الگوریتم وزن جهت‌دار نبودن یـال‌ها هم مشکلی ایجاد نمـی‌کند و مـی‌توان به منظور یـال‌های غیر جهت‌دار دو یـال فرض کرد.

فرض کنید $1 \le ‌s \le n$ کـه در آن رأس ‌$s$ رأس آغاز هست و فرض کنید: الگوریتم وزن $$dist(s) = 0$$ و به ازای هر $v\neq s$: $$dist(v) = \infty$$ فرض کنید مجموعه‌ی $T$ برابر رئوسی باشد کـه تا کنون کم وزن‌ترین مسیر آن‌ها را پیدا کرده‌ایم. این الگوریتم درون هر مرحله نزدیک‌ترین رأس بـه $s$ را کـه تا کنون بـه مجموعه‌ی ‌$T$ اضافه نشده را انتخاب مـی‌کند (مثلا ‌$x$) و آن را بـه مجموعه‌ی $T$ اضافه مـی‌کند و فاصله‌ی دیگر رأس‌ها را با توجه بـه فاصله‌‌ی $x$ بروز مـی‌کند. بـه ازای هر رأس $v$ خارج $T$: $$dist(v) = min\Big(dist(v), dist(x) + w(x, v)\Big)$$ کـه در آن $w(x, v)$ برابر وزن یـال بین $x$ و $v$ است. این الگوریتم درون هر مرحله رأسی را کـه کوتاه‌ترین فاصله‌ی آن که تا $s$ پیدا شده‌ هست را بـه $T$ اضافه مـی‌کند. زیرا کوتاه ترین مسیر این رأس از یکی از رأس‌های $T$ مـی‌گذرد کـه در مراحل قبلی فاصله آن‌ها بدست آمده و دیگر رئوس را بروز کرده‌اند.

در گراف زیر، الگوریتم وزن روند اجرای این الگوریتم را مـی‌توانید مشاهده کنید

در صورت منفی بودن یـال‌ها فرض اینکه درون هر مرحله رأسی کـه کوتاه‌ترین مسیر آن پیدا شده اضافه مـی‌شود زیر سوال مـی‌رود. زیرا این رأس مـی‌تواند بدون استفاده از رأس‌های $T$ و یـال‌های منفی مسیری کوتاه‌تر بـه ‌$s$ پیدا کند.

به ازای هر رأس حتما روند بالا را طی کنیم. یعنی دنبال آن بگردیم و همـه‌ی همسایـه‌های آن را پیمایش کنیم. بعد پیچیدگی زمانی برنامـه از $O(n \times n) = O(n^2)$ است. هر چند مـی‌توان با استفاده از داده ساختار هرم پیـاده‌سازی از $O\Big(e \times lg(n)\Big)$ ارائه داد.

شبه کد:

function Dijkstra(s): dist[s] = 0 for each vertex v in Graph: // Initializations if v ≠ s dist[v] = infinity end if end for while Size(T) ≠ n : // The main loop u := vertex not in T with min dist[u] add u to T for each neighbor v of u: dist[v] = min(dist[v], dist[u]+w[u][v]) end for end while end function

Dijkstra.cpp #include <iostream> using namespace std; const int MAXN = 1000 + 10; const int INF = 1000*1000*1000; int n, m; int adj[MAXN][MAXN]; int w[MAXN][MAXN]; int dist[MAXN]; int mark[MAXN]; void readInput(){ cin >> n >> m; for(int i=0; i<m; ++i){ int v, u, z; cin >> u >> v >> z; adj[u][v] = 1; w[u][v] = z; } } void dijkstra(int s){ dist[s] = 0; for(int i=0; i<n; ++i) if(i!=s) dist[i] = INF; for(int rep=0; rep<n; ++rep) { int u = -1; int du = INF; for(int i=0; i<n; ++i) if(!mark[i] && dist[i] <= du){ u = i; du = dist[i]; } mark[u] = 1; for(int v=0; v<n; ++v) if(adj[u][v]) dist[v] = min(dist[v], dist[u]+w[u][v]); } } void writeOutput(){ for(int i=0; i<n; ++i) cout << dist[i] << " "; cout << endl; } int main(){ readInput(); dijkstra(0); writeOutput(); return 0; }

مـی‌توان یـافتن نزدیک‌ترین رأس درون هر مرحله را بـه کمک این داده ساختار انجام داد. درون این صورت حتما گراف را بـه صورت لیست مجاورت نگه داریم. کـه در $C++$ به منظور راحتی کار از $Set$ استفاده مـی کنیم.

Dijkstra.cpp #include <iostream> #include <vector> #include <set> using namespace std; const int MAXN = 1000*100 + 10; const int INF = 1000*1000*1000; typedef pair<int, int> pii; int n, m; vector<int> adj[MAXN]; vector<int> w[MAXN]; set<pii> q; int dist[MAXN]; void readInput(){ cin >> n >> m; for(int i=0; i<m; ++i){ int v, u, z; cin >> u >> v >> z; adj[u].push_back(v); w[u].push_back(z); } } void dijkstra(int s){ dist[s] = 0; for(int i=0; i<n; ++i) if(i!=s) dist[i] = INF; for(int i=0; i<n; ++i) q.insert(pii(dist[i], i)); while(!q.empty()) { set<pii> :: iterator it = q.begin(); int u = it->second; q.erase(it); for(int i=0; i<adj[u].size(); ++i){ int v = adj[u][i]; q.erase(pii(dist[v], v)); dist[v] = min(dist[v], dist[u]+w[u][i]); q.insert(pii(dist[v], v)); } } } void writeOutput(){ for(int i=0; i<n; ++i) cout << dist[i] << " "; cout << endl; } int main(){ readInput(); dijkstra(0); writeOutput(); return 0; }