کوتاه ترین مسیر از یک راس با الگوریتم بلمن فورد Bellman-Ford
یکی از الگوریتم هایی که برای پیدا کردن کوتاه ترین مسیر از یک راس ( راس مبدا – source vertex ) به سایر راس ها در گراف استفاده می شود الگوریتم بلمن فورد یا Bellman-Ford است. البته الگوریتم مشهور دیگری هم به اسم Dijkstra هست که احتمالا با آن آشنایی دارید ولی الگوریتم Dijkstra به هیچ وجه قابلیت گرفتن یک گراف با یال منفی را ندارد. ولی الگوریتم بلمن فورد قابلیت گرفتن گراف با یال های منفی را دارد.
در شکل زیر یک گراف جهت دار را می بینید که کوتاه ترین مسیر از راس ۰ به تمام راس ها در آن محاسبه شده و در گوشه ی سمت چپ پایین تصویر نوشته شده است(البته در تصویر پایین یک قسمتی نوشتم Adjacency List که اشتباه است و به آن توجه نکنید، در واقع آن روشی است که گراف را از ورودی خوانده ام. این روش در سوال های مسابقه های برنامه نویسی رایج است. که فرمت ورودی را در آخر کد شرح داده ام) .
اگر یک گراف دارای یال منفی باشد می تواند کوتاه ترین مسیر در آن از یک راس به سایر راس ها وجود داشته باشد ولی اگر در گراف دوری داشته باشیم که مجموع جمع وزن یال های آن منفی باشد کوتاه ترین مسیر از یک راس به سایر راس ها وجود ندارد چون می توانیم بی نهایت بار روی دور حرکت کنیم و هزینه ی مسیر را کم تر کنیم. مانند تصویر زیر که در آن حلقه ای منفی وجود دارد:
ولی اگر آن یال منفی هشت را با منفی سه جایگزین کنیم مشکلی پیش نمی آید چون دور منفی نداریم. در تصویر زیر کوتاه ترین مسیر ها را می بینید:
قبل از اینکه بریم سراغ الگوریتم بلمن فورد، تابع Relax را شرح می دهیم. این تابع فاصله سورس تا دو راس ابتدا و انتهای یک یال جهت دار می گیرد و همین طور وزن یال را و سپس فاصله ی سورس تا راس انتهای یال را به صورت زیر آپدیت می کند.
در الگوریتم بلمنف ورد، برای هر راس دو ویژگی در نظر می گیریم یکی distance که فاصله ی راس سورس تا آن راس است و در آخر کار قرار است کوتاه ترین فاصله از راس سورس تا آن راس در آن قرار داشته باشد. و دومین ویژگی parent است که مشخص می کند پدر یک راس کدام راس است در تصویر بالا کوتاه ترین مسیر بین ۰ و ۱ برابر ۱ ۲ ۳ ۰ است یعنی برای اینکه از ۰ به یک ۱ آمده باشیم باید قبل از آن به ۲ برویم یعنی پدر یک برابر دو است و قبل از اینکه از ۰ به ۲ برویم باید به ۳ برویم یعنی پدر ۲ برابر سه است.
به تصویر زیر توجه کنید که دو راس u و v در آن وجود دارد و یالی با وزن ۵ از راس u خارج می شود و به v وارد می شود. فرض کنید که ما قبلا یک مسیری از راس سورس (source) تا v پیدا کرده ایم و طول آن ۱۳ است و همین طور یک مسیر دیگر از سورس تا راس u پیدا کرده ایم و طول آن ۳ است. تابع relax می بیند، فاصله مسیری که قبلا از راس سورس تا v رفته ایم آیا از مسیری که از سورس تا u رفته ایم به علاوه ی وزن یالی که از u خارج و به v وارد می شود، کمتر است یا نه ! اگر فاصله ی سورس تا u به علاوه ی وزن یال u به سمت v کمتر از فاصله سورس تا v باشد به این معنی است که مسیری کوتاه تر از سورس به v از طریق u پیدا کرده ایم که از مسیر قبلی سورس تا v کوتاه تر است. در نتیجه فاصله ی سورس تا v را آپدیت می کنیم و پدر v را برابر با u می کنیم. و اگر هم فاصله ی سورس تا u به علاوه ی وزن یال بیشتر از فاصله ی سورس تا v بود چیزی را آپدیت نمی کنیم زیرا همان مسیر قبلی تا از سورس تا v کوتاه تر از مسیر راس سورس تا u به علاوه ی یالی که از u خارج می شود و به v وارد می شود است.
در زیر کد تابع relax را می بینید :
1 2 3 4 5 6 7 8 9 10 11 12 13 | template <typename weightType> void relax( vector<weightType> &distance , vector<int> &parent , int startOfEdge, int endOfEdge, weightType weightOfEdge ) { if(distance[endOfEdge] > distance[startOfEdge] + weightOfEdge) { distance[endOfEdge] = distance[startOfEdge] + weightOfEdge; parent[endOfEdge] = startOfEdge; } } |
آرگومان های تابع relax:
distance : یک وکتور است به تعداد راس های گراف که خانه ی i ام آن فاصله ی سورس تا راس i ام است.
parent : یک وکتور به طول تعداد راس های گراف است که خانه ی i ام آن پدر راس i است.
startOfEdge: راس آغازین یال است.
endOfEdge: راسی است که یال به آن منتهی می شود.
weightofEdge : وزن یال است. از آنجایی که ممکن است وزن یال ها را بخواهید اعشاری تعریف کنید نوع وزن یال ها Template تعریف شده است.
بعد از تابع relax به سراغ تابع initial single source می رویم. این تابع فاصله ی تمام سورس تا تمام راس ها را برابر بی نهایت (یک مقدار بزرگ) قرار می دهد. و فاصله سورس تا خود سورس را برابر صفر می کند. و همین طور پدر همه ی راس ها را برابر ۱- می گذارد. یعنی ابتدا هیچ راسی پدرش مشخص نشده است. در زیر کد تابع relax را می بینیم:
1 2 3 4 5 6 7 8 9 | void initial_single_source(vector<weightType> &distance, vector<int> &parent, int source) { for(size_t i = 0; i < distance.size()/*number of vertices*/; ++i) { distance[i] = numeric_limits<weightType>::max() / 2; parent[i] = -1; } distance[source] = 0; } |
آرگومان ها:
source : راسی است که می خواهیم کوتاه ترین مسیر از آن راس به سایر راس ها را به دست بیاریم.
قبل از اینکه به سراغ الگوریتم Bellman-Ford برویم نشان بدهیم که با چه ساختمان داده ای گراف خود را نگاه می داریم. برای نگهداری گراف و راس ها و یال ها از
1 | vector< vector< pair<int,int> > > adjList(n); |
استفاده می کنیم. راه های مختلفی برای نگه داری گراف است یکی از آن ها ماتریس مجاورت است و یکی دیگر از آن ها لیست مجاورت است، این دو روش رایج ترین روش ها برای نگه داری گراف هستند. adjList یک لیست مجاورت است. adjList یک وکتور(vector) از وکتور ها است که هر وکتور درون آن یک pair است. adj List یک وکتور از وکتور ها است که خانه ی i ام آن شامل یک وکتور است که یال های خارج شده از راس i را نگه می دارد.
خانه ی i ام وکتور بیرونی شامل یک وکتور است که pair هایی را نگه می دارد. هر کدام از این pair ها نشان دهنده ی یک یال است. هر pair دو قسمت دارد قسمت اول( first ) و دوم ( second ). قسمت اول pair در اینجا راسی را نشان می دهد که یالی که از خانه ی i ام خارج شده به آن وارد شده است و قسمت دوم pair نشان دهنده ی وزن یال است. این روش نگه داری گراف بسیار مرسوم است و در الگوریتم های بعدی هم احتمالا از این روش استفاده کنیم. در صورتی که متوجه نشدید می توانید به تصویر زیر دقت کنید:
خوب حالا برویم سراغ خود الگوریتم bellman-ford برای محاسبه ی کوتاه ترین مسیر از یک راس به سایر راس ها. در یک گراف که n راس دارد هر مسیر ساده ای از یک راس تا یک راس دیگر در صورتی یک راس را بیش از یک بار نبینیم حداکثر n – 1 یال وجود دارد. یک مسیر بین دو راس می تواند شامل هیچ راسی دیگری نباشد در این صورت هر دو راس به صورت مستقیم به هم وصل شده اند. یا بین دو راس n – 2 راس دیگر وجود داشته باشد در این صورت در مسیر n – 1 یال داریم.
فرض کنید یک گراف را با استفاده از تابع initial single source مقدار دهی اولیه کرده ایم. بعد از این کار فاصله ی همه راس ها تا راس سورس برابر بینهایت (یک مقدار بزرگ) است بجز خود سورس که فاصله اش با خودش برابر صفر است. در ابتدا برای تمام یال های گراف تابع relax را فرا می خوانیم. خوب چه اتفاقی می افتد بعد از فراخوانی تابع ریلکس برای تمام یال ها؟ راس هایی که مستقیم به سورس هستند فاصله شان تا سورس آپدیت می شود و مقدارشان از بی نهایت به یک مقدار مشخص تغییر پیدا می کند. سایر راس ها چطور؟ بستگی به ترتیب ریلکس کردن یال ها دارد ممکن است مقدارشان آپدیت شود و یا همان بینهایت بماند. فرض کنید یک یال را ریلکس می کنیم بطوری که یال های متصل به آن قبل از آن ریلکس نشده است در نتیجه در سر آغازین یال مقدار بی نهایت است و سر پایانی آن هم بی نهایت می ماند. و از آن طرف هم مقدار فاصله ی بعضی از راس ها آپدیت می شود ولی این دلیل بر آن نیست که مقدار آپدیت شده فاصله سورس تا آن راس کوتاه ترین مسیر باشد. چون ممکن است کوتاه ترین مسیر بین راس تا یک نود شامل یک راس باشد و بار اول relax کردن تمام یال ها فقط زمانی معتبر است که کوتاه ترین مسیر از سورس تا یک راس شامل هیچ راس دیگری نباشد و دو راس مستقیم به هم وصل شده باشند. به همین دلیل برای بار دوم تمام یال ها را relax می کنیم. بعد از این کار ممکن است بعضی از راس ها آپدیت شوند و بعضی ها نشوند. در این مرحله در صورتی که کوتاه ترین فاصله ی از راس سورس تا یک راس شامل دو یال (یک راس در میان دو راس) باشد دیگر با relax کردن های بیشتر مقدار آن تغییر نمی کند. ولی برای بعضی ها مقدار distance قابل قبول نیست زیرا ممکن است کوتاه ترین مسیر از راس سورس تا یک راس شامل سه یال (دو راس در وسط) باشد در این صورت باید یک بار دیگر تمام یال ها را relax کنیم. از آنجایی که در گرافی که n راس دارد حداکثر یک مسیر می تواند شامل n – 1 یال باشد باید n – 1 بار تمام یال ها را relax کنیم . و این همان کاری است که الگوریتم Bellman-Ford می کند. در زیر تصویری از این روش را می بینید که ۴ بار تمام یال ها ریلکس شده اند و هر بار تغییرات با رنگ پررنگ مشخص شده است.
وقت نشد ببینم لایسنس کپی رایت کتاب سی ال آر اس چیست به همین خاطر اسم کتاب را داخل تصویر گذاشتم. بعدا چک می کنم اگر مشکل داشت خودم تصویرش را می سازم.
در زیر کد الگوریتم Bellman-Ford را که با سی پلاس پلاس نوشته شده است را می بینید:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | template <typename weightType> bool Bellman_Ford( vector< vector< pair<int,weightType> > > &adjList , vector<weightType> &distance , vector<int> &parent , int sourceVertex ) { initial_single_source(distance, parent, sourceVertex); /* Find all shortest path by relaxing * all edges number of vertices mines * one times */ for(size_t k = 0; k < adjList.size() - 1; ++k) { /*relax all edges of graph*/ for(size_t i = 0; i < adjList.size(); ++i) { for(size_t j = 0; j < adjList[i].size(); ++j) { relax(distance, parent, i/*start vertex of the edge*/ , adjList[i][j].first/*end vertex of the edge*/ , adjList[i][j].second/*weight of the edge*/ ); } } } /*determine do not exist negative cycles (true) or exist (false)*/ for(size_t i = 0; i < adjList.size(); ++i) { for(size_t j = 0; j < adjList[i].size(); ++j) { /*u-->v v.distance > u.distance + weight*/ if(distance[adjList[i][j].first] > distance[i] + adjList[i][j].second) { return false; } } } return true; } |
که همه آرگومان های ورودی آن را در بالا شرح داده ایم. خروجی این تابع یک مقدار bool است که اگر true باشد نشان می دهد دوری در گراف که مجموع یال های آن منفی شود نداریم و مقدار distance و parent معتبر است. ولی اگر false باشد یعنی دوری داریم که مجموع یال های روی آن منفی است در نتیجه آن گراف کوتاه ترین مسیر ندارد و مقادیر distance و parent نامعتبر است.
چگونه تشخص دهیم دوری داریم که مجموع یال های آن منفی است؟ این کار بسیار ساده است. اگر بعد از n – 1 بار relax کردن تمام یال ها بتوانیم یالی را پیدا کنیم که بعد از ریلکس کردن آن یال فاصله ی سورس تا سر یال آپدیت شود آنگاه می توان گفت که دور با مجموع منفی در گراف داریم همان دو for تو در توی پایانی کد بالا این کار را می کند.
کد الگوریتم بلمن فورد به زبان سی پلاس پلاس
در کد سی پلاس پلاس (++C) زیر کد کلی الگوریتم کوتاه ترین مسیر bellman ford را می بینید به همراه یک تابع main که در تابع main ماتریس از ورودی گرفته شده است و کوتاه ترین مسیر از راس ۰ به سایر راس ها حساب شده است و مسیر و فاصیله برای آن ها چاپ شده است. در پایان کد هم یک سری ورودی داده شده است که به صورت کامنت شده هستند که می توانید آن ها را جهت تست کد استفاده کنید. فرمت ورودی گراف هم در پایان کد در قسمت کامنت شده آورده شده است. که با خواندن کد هم آن را متوجه می شوید.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 | #include <bits/stdc++.h> using namespace std; template <typename weightType> void initial_single_source(vector<weightType> &distance, vector<int> &parent, int source) { for(size_t i = 0; i < distance.size()/*number of vertices*/; ++i) { distance[i] = numeric_limits<weightType>::max() / 2; parent[i] = -1; } distance[source] = 0; } template <typename weightType> void relax( vector<weightType> &distance , vector<int> &parent , int startOfEdge, int endOfEdge, weightType weightOfEdge ) { if(distance[endOfEdge] > distance[startOfEdge] + weightOfEdge) { distance[endOfEdge] = distance[startOfEdge] + weightOfEdge; parent[endOfEdge] = startOfEdge; } } template <typename weightType> bool Bellman_Ford( vector< vector< pair<int,weightType> > > &adjList , vector<weightType> &distance , vector<int> &parent , int sourceVertex ) { initial_single_source(distance, parent, sourceVertex); /* Find all shortest path by relaxing * all edges number of vertices mines * one times */ for(size_t k = 0; k < adjList.size() - 1; ++k) { /*relax all edges of graph*/ for(size_t i = 0; i < adjList.size(); ++i) { for(size_t j = 0; j < adjList[i].size(); ++j) { relax(distance, parent, i/*start vertex of the edge*/ , adjList[i][j].first/*end vertex of the edge*/ , adjList[i][j].second/*weight of the edge*/ ); } } } /*determine do not exist negative cycles (true) or exist (false)*/ for(size_t i = 0; i < adjList.size(); ++i) { for(size_t j = 0; j < adjList[i].size(); ++j) { /*u-->v v.distance > u.distance + weight*/ if(distance[adjList[i][j].first] > distance[i] + adjList[i][j].second) { return false; } } } return true; } vector<int> find_path(vector<int> &parent, int source, int distance) { int curVertex = distance; vector<int> path; while(distance != -1) { path.push_back(distance); distance = parent[distance]; } if(path.back() != source) { /*there is no path between them*/ path.clear(); } reverse(path.begin(), path.end()); return path; } int main() { int n /*Vertex*/ ,m /*Number of edge*/; cin >> n >> m; /*we have n vertices.Vertices numbered from zero to n-1*/ vector< vector< pair<int,int> > > adjList(n); /*Adjacency List Of Graph*/ vector< int > distance(n); /*distance of vertices from source*/ vector< int > parent(n); /*Parent of vertices*/ int startOfEdge, endOfEdge, weight; for(int i = 0; i < m; ++i) { /*read undirected edges*/ cin >> startOfEdge >> endOfEdge >> weight; adjList[startOfEdge].push_back( pair<int,int>(endOfEdge, weight) ); //adjList[endOfEdge].push_back( pair<int,int>(startOfEdge, weight) ); /*if graph is not directed uncomment this line*/ } cout << endl; int source_vertex = 0; bool no_negative_cycle = Bellman_Ford(adjList, distance, parent, source_vertex); if(no_negative_cycle) { /*print all shortest path from source*/ vector<int> path; for(int i = 0; i < n; ++i) { path = find_path(parent,source_vertex,i); cout << "distance between " << source_vertex << " and " << i << " is "; if(distance[i] >= numeric_limits<int>::max() / 2) { cout << "INFINIT" << endl; } else { cout << distance[i] << endl; } if(path.size() > 0) { cout << "Path: "; for(int i = 0; i < path.size(); ++i) { cout << path[i] << " "; } cout << endl; } else { cout << "There is no path between them!" << endl; } } } else { cout << "Graph has negative cycle!" << endl; } return 0; } /* input format: number_of_vertices number_of_edges start_of_edge end_of_edge weight_of_edge start_of_edge end_of_edge weight_of_edge . . . start_of_edge end_of_edge weight_of_edge inputs example: 5 6 0 1 2 1 4 5 1 2 4 0 3 1 3 2 3 2 4 1 or 5 7 0 1 2 1 4 5 1 2 4 0 3 1 3 2 3 2 4 1 2 1 -3 or 5 7 0 1 2 1 4 5 1 2 4 0 3 1 3 2 3 2 4 1 2 1 -8 */ |
در زیر یک نمونه از اجرای برنامه را می بینید:
هزینه ی الگوریتم:
bellman ford در مجموع به تعداد راس ها (V) منهای یک عمل relax کردن تمام یال ها را انجام می دهد و در هر بار به تعداد تمام یال ها (E) عمل ریلکس کردن را انجام می دهند که درنتیجه هزینه ی کلی الگوریتم برابر با Θ(V.E) می شود.
در پست بعدی در مورد Dijkstra صحبت می کنیم.
خیلی خوب بود
تفاوتش با الگوریتم فروشنده دوره گرد چیه اونوقت؟
به نظرم یکی اومدن!!!
این الگوریتم کوتاه ترین مسیر از یک راس به سایر راس ها را پیدا می کند. ممکن است در کوتاه ترین مسیر از یک راس به راس دیگر هیچ راس دیگری وجود نداشته باشد یا چندین راس(نود) وجود داشته باشد.
ولی در فروشنده ی دوره گرد n راس در گراف داریم و می گوید باید یک مسیر پیدا کنید که از راس x شروع شود و در پایان دوباره به راس x برسد.و این مسیر باید طولش مینیموم باشد.
سلام…
اگر ممکنه از تجاربتون در المپیاد هم بنویسید…
فکرکنم رتبه ۶ شده بودید!
ممنون
سلام – رتبه ی ۵ شده بودم. چشم حتما تا یک ماه دیگه یک پست کامل می نویسم
آها!
ببخشید پس جایی که من دیدم رتبه ی شما رو اشتباه زده بودن….!!
رتبه ۵ بسیار عالیه
منتظر تجارب عالی شما هستم
ممنون از لطفتون