کوتاهترین مسیر در نمودار ، الگوریتم dijkstra است. یافتن کوتاهترین مسیرها از یک راس داده شده به همه رئوس های دیگر توسط الگوریتم dijkstra. تنظیم وظیفه جدید از مصاحبه

با استفاده از الگوریتم Dijkstra مشکل پیدا کردن کوتاهترین مسیر را حل کنید.
کوتاهترین مسیر را از X0 تا X7 پیدا کنید. نمودار توسط عناصر ماتریس هزینه ارائه شده است

این نمودار را بسازید

بیایید با عنصر X0 شروع کنیم و برچسب 0 را به آن اختصاص دهیم ، همه همسایگان خود را در نظر بگیرید ، زیرا هنوز هیچ علامتی وجود ندارد ، سپس طول های مربوطه را به آنها اختصاص دهید:

همه همسایگان X0 در نظر گرفته می شوند ، آن را علامت بزنید و به بالای X1 بروید. همسایگان آن X0، X2، X4 هستند اما X0 دارای برچسب است ، ما آن را در نظر نمی گیریم. برای X2: ترک یک نشان.

برای X4: برچسب را جایگزین کنید. همه همسایگان راس X1 در نظر گرفته می شوند ، آن را علامت گذاری کنید

به بالای X2 بروید. همسایگان آن X0، X1، X3، X4، X5، X6 هستند اما X0، X1 مشخص شده اند ، ما آنها را در نظر نمی گیریم.
برای X3: ترک یک نشان.
برای X5: برچسب را جایگزین کنید.
برای X4: ترک یک نشان.
برای X6: برچسب را جایگزین کنید.
همه همسایگان راس X2 در نظر گرفته شده است ، ما آن را علامت گذاری می کنیم.

به بالای X3 بروید. همسایگان آن X0 ، X2 ، X6 هستند ، اما X0 ، X2 دارای برچسب هستند ، ما آنها را در نظر نمی گیریم.
برای X6: ترک یک نشان.
همه همسایگان راس X3 در نظر گرفته شده است ، ما آن را علامت گذاری می کنیم.

به بالای X4 بروید. همسایگان آن X1، X2، X5، X7 هستند اما X1، X2 دارای برچسب هستند ، ما آنها را در نظر نمی گیریم.
برای X5: برچسب را جایگزین کنید.
برای X7: برچسب را جایگزین کنید.
همه همسایگان راس X4 در نظر گرفته شده است ، ما آن را علامت گذاری می کنیم.

به بالای X5 بروید. همسایگان آن X2، X4، X6، X7 هستند اما X2، X4 دارای برچسب هستند ، ما آنها را در نظر نمی گیریم.
برای X6: ترک یک نشان.
برای X7: ترک یک نشان.
همه همسایگان راس X5 در نظر گرفته شده است ، ما آن را علامت گذاری می کنیم.

به بالای X6 بروید. همسایگان آن X2، X3، X5، X7 اما X2، X3، X5 مشخص شده اند ، ما آنها را در نظر نمی گیریم.
برای X7: ترک یک نشان.
همه همسایگان راس X6 بررسی می شوند ، ما آن را علامت گذاری می کنیم. و باقیمانده X7 را علامت گذاری کنید ، تمام رئوسها در نظر گرفته می شوند.

نتیجه گیری: کوتاهترین مسیر X0 تا X7 طول آن 101 طول است: X7-X4-X1-X0.

الگوریتم Dijkstra (الگوریتم Dijkstra) یک الگوریتم گراف است که توسط دانشمند هلندی Edsger Dijkstroy در سال 1959 ابداع شده است. کوتاهترین مسیرها را از یکی از رئوس های نمودار به سایر موارد می یابد. الگوریتم کار می کند فقط برای نمودارهای بدون لبه های وزن منفی.

اجرای الگوریتم را به عنوان مثال از نمودار نشان داده شده در شکل در نظر بگیرید.

فرض کنید می خواهید از اولین قله تا همه موارد دیگر کوتاهترین فاصله را پیدا کنید.

حلقه ها راسها را نشان می دهند ، خطوط مسیرهای بین آنها (لبه های نمودار) را نشان می دهند. حلقه\u200cها تعداد رأسها را نشان می دهند ؛ در بالای لبه ها ، "قیمت" آنها نشان داده شده است - طول مسیر. یک برچسب به رنگ قرمز در کنار هر راس مشخص شده است - طول کوتاهترین مسیر این راس از راس 1.

گام اول. برای مثال ما مرحله الگوریتم Dijkstra را در نظر بگیرید. حداقل برچسب دارای راس 1 است. همسایگان آن راسهای 2 ، 3 و 6 هستند.

اولین همسایه به نوبه خود راس 1 است ، vertex 2 ، زیرا مسیر رسیدن به آن حداقل است. طول مسیر داخل آن از طریق vertex 1 برابر است با مقدار مقدار برچسب راس 1 و طول لبه که از 1 به 2 می رود ، یعنی 0 + 7 \u003d 7. این کمتر از برچسب فعلی vertex 2 ، بینهایت است ، بنابراین برچسب جدید 2 است. راس 7 است.

ما یک عمل مشابه با دو همسایه دیگر راس 1 - 3 و 6 انجام می دهیم.

همه همسایگان vertex 1 تأیید شده اند. حداقل فاصله فعلی تا اوج 1 نهایی در نظر گرفته شده و در معرض تجدید نظر نیست (ابتدا E. Dijkstra ثابت کرد که اینگونه است). آن را از نمودار عبور دهید تا توجه داشته باشید که از این قله بازدید شده است.

مرحله دوم. مرحله الگوریتم تکرار می شود. دوباره "نزدیکترین" قله های ناظر را می یابیم. این vertex 2 با برچسب 7 است.

باز هم ، ما سعی می کنیم برچسب های همسایگان راس انتخاب شده را کاهش دهیم ، سعی می کنیم از طریق راس 2 از آنها عبور کنیم. همسایگان قله 2 قله های 1 ، 3 و 4 هستند.

اولین همسایه vertex 2 vertex 1 است. اما از قبل بازدید شده است ، بنابراین ما با اولین راس هیچ کاری نمی کنیم.

همسایه بعدی vertex 2 vertex 3 است ، زیرا دارای حداقل برچسب راسهایی است که به عنوان بازدید نشده نشان داده شده است. اگر از طریق 2 به داخل آن بروید ، طول این مسیر برابر 17 خواهد بود (7 + 10 \u003d 17). اما برچسب فعلی راس سوم 9 است که کمتر از 17 است ، بنابراین برچسب تغییر نمی کند.

اگر همسایه دیگر vertex 2 vertex 4. باشد ، اگر از طریق مسیر 2 به داخل آن بروید ، طول این مسیر با مجموع کوتاهترین فاصله تا راس 2 و فاصله بین راسهای 2 و 4 برابر خواهد بود ، یعنی 22 (7 + 15 \u003d 22) . از سال 22<, устанавливаем метку вершины 4 равной 22.

همه همسایگان vertex 2 اسکن می شوند ، مسافت را تا آن مسدود کرده و در صورت بازدید آن را علامت بزنید.

مرحله سوم. ما مرحله الگوریتم را با انتخاب راس 3 تکرار می کنیم. پس از پردازش آن نتایج زیر را بدست می آوریم:

مراحل بعدی. مرحله الگوریتم را برای رئوس های باقی مانده تکرار کنید. اینها ترتیب ترتیب 6 ، 4 و 5 خواهند بود.

تکمیل الگوریتم. این الگوریتم زمانی پایان می یابد که دیگر پردازش یک راس واحد امکان پذیر نباشد. در این مثال ، تمام رئوسها از هم عبور می كنند ، با این وجود ، اشتباه است كه فرض كنیم كه در هر مثال اینگونه خواهد بود - بعضی از راسها اگر نتوانند به دست بیایند ، باقی مانده اند ، یعنی اگر گراف از هم جدا شود ، ممكن است بدون رمز باقی بماند. نتیجه الگوریتم در شکل آخر قابل مشاهده است: کوتاهترین مسیر از بالای 1 تا 2 7 است ، به 3 - 9 ، به 4 - 20 ، به 5 - 20 ، تا 6 - 11.

اجرای الگوریتم در زبان های مختلف برنامه نویسی:

C ++

#includ "stdafx.h" #includ با استفاده از namespace std؛ const int V \u003d 6؛ // الگوریتم Dijkstra از درجه اعتبار ساقط Dijkstra (int GR [V] [V] ، int st) (فاصله int [V] ، شمارش ، فهرست ، i ، u ، m \u003d st + 1؛ bool بازدید [V] ؛ برای (i \u003d 0؛ من "< "<\u003e "؛ cin \u003e\u003e start؛ Dijkstra (GR، start-1)؛ system (" مکث\u003e باطل ")؛)

پاسکال

برنامه DijkstraAlgorithm؛ از crt استفاده می کند؛ const V \u003d 6؛ inf \u003d 100000؛ نوع بردار \u003d آرایه عدد صحیح؛ var start: عدد صحیح؛ const GR: array of integer \u003d ((0، 1، 4، 0، 2، 0)، (0، 0، 0، 9، 0، 0)، (4، 0، 0، 7، 0، 0)، (0 ، 9 ، 7 ، 0 ، 0 ، 2) ، (0، 0، 0، 0، 0، 8)، (0، 0، 0، 0، 0، 0، 0، 0))؛ (الگوریتم Dijkstra) روش Dijkstra (GR: آرایه عدد صحیح؛ st: عدد صحیح)؛ تعداد متغیر ، شاخص ، من ، تو ، متر ، دقیقه: عدد صحیح؛ فاصله: بردار؛ بازدید: آرایه از boolean؛ شروع m: \u003d st؛ برای i: \u003d 1 تا V فاصله را شروع کنید [i]: \u003d inf؛ بازدید [i]: \u003d false؛ پایان؛ فاصله: \u003d 0؛ برای شمارش: \u003d 1 تا V-1 min شروع می شود: \u003d inf؛ برای i: \u003d 1 تا V انجام دهید اگر (بازدید نشده [i]) و (مسافت [i]<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) و (فاصله [u]<>inf) و (فاصله [u] + GR inf then writeln (m، "\u003e"، i، "\u003d"، فاصله [i]) other دیگری نویسنده (m، "\u003e"، i، "\u003d"، "مسیر در دسترس نیست")؛ پایان؛ (بلوک اصلی برنامه) clrscr را شروع می کنید. نوشتن ("شروع راس \u003e\u003e")؛ بخوانید (شروع) Dijkstra (GR ، شروع)؛ پایان.

جاوا

وارد کردن java.io.BufferedReader؛ وارد کردن java.io.IOException؛ وارد کردن java.io.InputStreamReader؛ وارد کردن java.io.PrintWriter؛ وارد کردن java.util.ArrayList؛ وارد کردن java.util.Arrays؛ وارد کردن java.util.StringTokenizer؛ Solution کلاس عمومی (private static int INF \u003d Integer.MAX_VALUE / 2؛ int int n؛ // تعداد تعداد راس ها در intr خصوصی خصوصی برای digraph ؛ // تعداد راسها در ArrayList خصوصی دیجیتال) adj؛ // لیست مجاور ArrayList خصوصی وزن // وزن لبه در بولن خصوصی digraph مورد استفاده؛ // آرایه ای برای ذخیره اطلاعات در مورد قله های منتقل شده و گذشت نشده بین المللی؛ // آرایه برای ذخیره فاصله از راس شروع // آرایه اجداد مورد نیاز برای بازگرداندن کوتاهترین مسیر از vertex شروع خصوصی int int pred؛ int int؛ // شروع راس ، که از آن فاصله تا سایر افراد جستجو می شود خصوصی BufferedReader cin؛ cout printWriter خصوصی؛ شناسه خصوصی StringTokenizer؛ // روش شروع الگوریتم Dijkstra از vertex void dejkstra (int s) از فاصله اولیه شروع کار (dist [s] \u003d 0؛ // کوتاهترین فاصله تا راس شروع 0 برای (int iter \u003d 0؛ iter< n; ++iter) { int v = -1; int distV = INF; //выбираем вершину, кратчайшее расстояние до которого еще не найдено for (int i = 0; i < n; ++i) { if (used[i]) { continue; } if (distV < dist[i]) { continue; } v = i; distV = dist[i]; } //рассматриваем все дуги, исходящие из найденной вершины for (int i = 0; i < adj[v].size(); ++i) { int u = adj[v].get(i); int weightU = weight[v].get(i); //релаксация вершины if (dist[v] + weightU < dist[u]) { dist[u] = dist[v] + weightU; pred[u] = v; } } //помечаем вершину v просмотренной, до нее найдено кратчайшее расстояние used[v] = true; } } //процедура считывания входных данных с консоли private void readData() throws IOException { cin = new BufferedReader(new InputStreamReader(System.in)); cout = new PrintWriter(System.out); tokenizer = new StringTokenizer(cin.readLine()); n = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа start = Integer.parseInt(tokenizer.nextToken()) - 1; //инициализируем списка смежности графа размерности n adj = new ArrayList[n]; for (int i = 0; i < n; ++i) { adj[i] = new ArrayList()؛ // // اولیه سازی لیستی که وزن لبه ها در آن ذخیره می شود \u003d ArrayList جدید [n]؛ برای (int i \u003d 0؛ i< n; ++i) { weight[i] = new ArrayList()؛ // // نمودار مشخص شده توسط لیست لبه ها را برای (int i \u003d 0؛ i) بخوانید< m; ++i) { tokenizer = new StringTokenizer(cin.readLine()); int u = Integer.parseInt(tokenizer.nextToken()); int v = Integer.parseInt(tokenizer.nextToken()); int w = Integer.parseInt(tokenizer.nextToken()); u--; v--; adj[u].add(v); weight[u].add(w); } used = new boolean[n]; Arrays.fill(used, false); pred = new int[n]; Arrays.fill(pred, -1); dist = new int[n]; Arrays.fill(dist, INF); } //процедура восстановления кратчайшего пути по массиву предком void printWay(int v) { if (v == -1) { return; } printWay(pred[v]); cout.print((v + 1) + " "); } //процедура вывода данных в консоль private void printData() throws IOException { for (int v = 0; v < n; ++v) { if (dist[v] != INF) { cout.print(dist[v] + " "); } else { cout.print("-1 "); } } cout.println(); for (int v = 0; v < n; ++v) { cout.print((v + 1) + ": "); if (dist[v] != INF) { printWay(v); } cout.println(); } cin.close(); cout.close(); } private void run() throws IOException { readData(); dejkstra(start); printData(); cin.close(); cout.close(); } public static void main(String args) throws IOException { Solution solution = new Solution(); solution.run(); } }

گزینه ای دیگر:

وارد کردن java.io. *؛ وارد کردن java.util. *؛ کلاس عمومی Dijkstra (بخش خصوصی استاتیک Graph.Edge GRAPH \u003d (نمودار جدید.Edge ("a" ، "b" ، 7) ، Graph.Edge جدید ("a" ، "c" ، 9) ، Graph.Edge جدید ( "a" ، "f" ، 14) ، Graph.Edge جدید ("b" ، "c" ، 10) ، Graph.Edge جدید ("b" ، "d" ، 15) ، Graph.Edge جدید ("c "،" d "، 11) ، Graph.Edge جدید (" c "،" f "، 2) ، Graph.Edge جدید (" d "،" e "، 6) ، Graph.Edge جدید (" e "، "f" ، 9) ،) ؛ رشته ثابت استاتیک STAR START \u003d "a" ؛ انتهای ثابت استاتیک رشته نهایی \u003d "e" ؛ اصلی خالی استاتیک اصلی (استدلال رشته) (نمودار g \u003d نمودار جدید (GRAPH) ؛ g.dijkstra (شروع) ؛ g.printPath (خاتمه) ؛ //g.printAllPaths () ؛)) نمودار کلاس (نقشه نهایی خصوصی نمودار؛ // نقشه برداری از نام های vertex به اشیاء Vertex ، ساخته شده از مجموعه ای از Edges / ** یک لبه نمودار (فقط توسط سازنده Graph استفاده می شود) * / کلاس استاتیک عمومی Edge (عمومی نهایی String v1 ، v2؛ عمومی نهایی int dist؛ عمومی Edge (String v1، String v2، int dist) (this.v1 \u003d v1؛ this.v2 \u003d v2؛ this.dist \u003d dist؛)) / ** یک راس نمودار ، با نقشه های مربوط به vertices همسایه ها * / کلاس استاتیک عمومی Vertex پیاده سازی می کند (نام نهایی رشته عمومی؛ public int dist \u003d Integer.MAX_VALUE؛ // MAX_VALUE فرض بر این است که بینهایت عمومی Vertex قبلی \u003d null است؛ نقشه نهایی عمومی همسایگان \u003d HashMap جدید<>()؛ عمومی Vertex (نام رشته) (this.name \u003d name؛) private void printPath () (if (this \u003d\u003d this.prelimin) (System.out.printf ("٪ s"، this.name)؛)) دیگر اگر ( این.پیشه \u003d\u003d null) (System.out.printf ("٪ s (دست نیافته)" ، this.name)؛) موارد دیگر (this.prelimin.printPath ()؛ System.out.printf ("-\u003e٪ s ( ٪ d) "، this.name ، this.dist)؛)) public int CompareTo (other Vertex) (Return Integer.compare (dist، other.dist)؛)) / ** یک نمودار از مجموعه ای از لبه ها می سازد * / نمودار عمومی (لبه های لبه) (نمودار \u003d جدید HashMap<>(edge.l طول)؛ // یک گذرگاه برای یافتن همه راسها برای (Edge e: edge) (اگر (! Graph.containsKey (e.v1)) Graph.put (e.v1 ، Vertex جدید (e.v1)) ؛ اگر (! نمودار). حاویKK (e.v2)) Graph.put (e.v2 ، Vertex جدید (e.v2))؛) // گذر دیگری برای تنظیم راس همسایگان برای (Edge e: edge) (Graph.get (e.v1). cîran.put (graph.get (e.v2) ، e.dist)؛ //graph.get(e.v2).neighbours.put(graph.get(e.v1) ، e.dist)؛ // همچنین این کار را برای یک نمودار غیرمستقیم انجام دهید)) / ** dijkstra را با استفاده از یک راس منبع مشخص * / Public void dijkstra (رشته startName) اجرا می کند (اگر (! Graph.containsKey (startName)) (System.err.printf ("Graph doesn" t حاوی vertex start \\ "٪ s \\" \\ n "، startName)؛ Return؛) منبع Vertex نهایی \u003d Graph.get (startName)؛ NavigableSet q \u003d TreeSet جدید<>()؛ // راس های تنظیم شده برای (Vertex v: Graph.values \u200b\u200b()) (v.preicion \u003d v \u003d\u003d منبع؟ منبع: null؛ v.dist \u003d v \u003d\u003d منبع؟ 0: Integer.MAX_VALUE؛ q.add ( v)؛) dijkstra (q)؛ ) / ** اجرای الگوریتم dijkstra با استفاده از یک پشته باینری. * / private void dijkstra (نهایی NavigableSet q) (Vertex u، v؛ while (! q.isEmpty ()) (u \u003d q.pollFirst ()؛ // vertex با کوتاهترین فاصله (تکرار اول منبع بازگشت) اگر (u.dist \u003d\u003d Integer.MAX_VALUE) break؛ // ما می توانیم شما (و هر راس باقی مانده دیگر) را نادیده بگیریم زیرا آنها غیرقابل دسترسی هستند // به فواصل هر همسایه نگاه کنید. (Map.Entry a: u.neighbours.entrySet ()) (v \u003d a.getKey ()؛ // // همسایه در این تکرار نهایی int int alternativeDist \u003d u.dist + a.getValue ()؛ if (alternateDist< v.dist) { // shorter path to neighbour found q.remove(v); v.dist = alternateDist; v.previous = u; q.add(v); } } } } /** Prints a path from the source to the specified vertex */ public void printPath(String endName) { if (!graph.containsKey(endName)) { System.err.printf("Graph doesn"t contain end vertex \"%s\"\n", endName); return; } graph.get(endName).printPath(); System.out.println(); } /** Prints the path from the source to every vertex (output order is not guaranteed) */ public void printAllPaths() { for (Vertex v: graph.values()) { v.printPath(); System.out.println(); } } }

ج

#عبارتند از #عبارتند از #عبارتند از // # تعریف BIG_EXAMPLE typedef گره ساختار_ گره_t ، * heap_t؛ typedef struktur edge_t edge_t؛ struct edge_t (node_t * nd؛ / * هدف این لبه * / edge_t * خواهر و برادر ؛ / * برای لیست به تنهایی پیوندی * / int len؛ / * هزینه لبه * /)؛ struktur node_t (edge_t * edge؛ / * لیست جداگانه لبه ها * / node_t * از طریق؛ / * جایی که گره قبلی در کوتاهترین مسیر قرار دارد * / فاصله دو برابر ؛ / * فاصله از گره منشاء * / نام کاراکتر ؛ / * the ، er ، نام * / int heap_idx؛ / * پیوند به موقعیت heap برای به روزرسانی فاصله * /)؛ / * --- مدیریت لبه --- * / #ifdef BIG_EXAMPLE # تعریف BLOCK_SIZE (1024 * 32 - 1) #else # تعریف BLOCK_SIZE 15 #endif edge_t * edge_root \u003d 0، * e_next \u003d 0؛ / * مسائل مربوط به مدیریت حافظه را فراموش نکنید ، آنها علاوه بر این نکته نیز هستند. پیشگویی کنید e_next \u003d malloc (sizeof (edge_t)) * / add_edge (node_t * a ، node_t * b، double d) را ببندید (اگر (e_next \u003d\u003d edge_root ) (edge_root \u003d malloc (sizeof (edge_t) * (BLOCK_SIZE + 1))؛ edge_root.sibling \u003d e_next؛ e_next \u003d edge_root + BLOCK_SIZE؛) --e_next؛ e_next-\u003e nd \u003d b؛ e_next-\u003e len \u003d d؛ e_next -\u003e sibling \u003d a-\u003e edge؛ a-\u003e edge \u003d e_next؛) free_edges () (برای (؛ edge_root؛ edge_root \u003d e_next)) (e_next \u003d edge_root.sibling؛ free (edge_root)؛)) / * - موارد صف اولویتی --- * / heap_t * heap؛ int heap_len؛ void set_dist (node_t * nd، node_t * via، double d) (int i، j؛ / * از قبل مسیر بهتری را می دانستیم * / if (nd-\u003e via && d\u003e \u003d nd-\u003e dist) Return؛ / * ورود پشته موجود را پیدا کنید ، یا یک مورد جدید ایجاد کنید * / nd-\u003e dist \u003d d؛ nd-\u003e via \u003d via؛ i \u003d nd-\u003e heap_idx؛ if (! i) i \u003d ++ heap_len؛ / * upheap * / for (؛ i\u003e 1 && nd-\u003e dist< heap->فاصله؛ i \u003d j) (heap [i] \u003d heap [j]) -\u003e heap_idx \u003d i؛ heap [i] \u003d nd؛ nd-\u003e heap_idx \u003d i؛ ) node_t * pop_queue () (node_t * nd، * tmp؛ int i، j؛ اگر (! heap_len) برگشت 0؛ / * عنصر پیشرو را حذف کنید ، عنصر دم را در آنجا بکشید و پایین / * nd \u003d heap؛ tmp \u003d heap؛ for (i \u003d 1؛ i< heap_len && (j = i * 2) <= heap_len; i = j) { if (j < heap_len && heap[j]->dist\u003e heap-\u003e dist) j ++؛ if (heap [j] -\u003e dist\u003e \u003d tmp-\u003e dist) break؛ (heap [i] \u003d heap [j]) -\u003e heap_idx \u003d i؛ ) heap [i] \u003d tmp؛ tmp-\u003e heap_idx \u003d i؛ بازگشت؛ ) / * --- چیزهای Dijkstra؛ گره های غیر قابل دستیابی هرگز وارد صف نمی شوند --- * / void calc_all (node_t * شروع) (node_t * سرب ؛ edge_t * e؛ set_dist (شروع ، شروع ، 0) ؛ در حالی که ((سرب \u003d pop_queue ())) برای ( e \u003d سرب-\u003e لبه؛ e؛ e \u003d e-\u003e خواهر و برادر) set_dist (e-\u003e nd، سرب، سرب-\u003e dist + e-\u003e len)؛) void show_path (node_t * nd) (if (nd-\u003e از طریق \u003d\u003d nd) printf ("٪ s" ، نام-\u003e نام) ؛ در غیر اینصورت (! nd-\u003e via) printf ("٪ s (دست نیافته)" ، نام-\u003e\u003e) ؛ دیگری (show_path (nd-\u003e از طریق) ؛ printf ("-\u003e٪ s (٪ g)" ، nd-\u003e name ، nd-\u003e dist)؛)) int main (void) (#ifndef BIG_EXAMPLE int i؛ # تعریف N_NODES ("f" - " a "+ 1) node_t * nodes \u003d calloc (sizeof (node_t) ، N_NODES) ؛ برای (i \u003d 0؛ من< N_NODES; i++) sprintf(nodes[i].name, "%c", "a" + i); # define E(a, b, c) add_edge(nodes + (a - "a"), nodes + (b - "a"), c) E("a", "b", 7); E("a", "c", 9); E("a", "f", 14); E("b", "c", 10);E("b", "d", 15);E("c", "d", 11); E("c", "f", 2); E("d", "e", 6); E("e", "f", 9); # undef E #else /* BIG_EXAMPLE */ int i, j, c; # define N_NODES 4000 node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i < N_NODES; i++) sprintf(nodes[i].name, "%d", i + 1); /* given any pair of nodes, there"s about 50% chance they are not connected; if connected, the cost is randomly chosen between 0 and 49 (inclusive! see output for consequences) */ for (i = 0; i < N_NODES; i++) { for (j = 0; j < N_NODES; j++) { /* majority of runtime is actually spent here */ if (i == j) continue; c = rand() % 100; if (c < 50) continue; add_edge(nodes + i, nodes + j, c - 50); } } #endif heap = calloc(sizeof(heap_t), N_NODES + 1); heap_len = 0; calc_all(nodes); for (i = 0; i < N_NODES; i++) { show_path(nodes + i); putchar("\n"); } #if 0 /* real programmers don"t free memories (they use Fortran) */ free_edges(); free(heap); free(nodes); #endif return 0; }

پی اچ پی

$ edge، "هزینه" \u003d\u003e $ edge)؛ $ همسایگان [$ edge] \u003d آرایه ("پایان" \u003d\u003e $ edge ، "هزینه" \u003d\u003e $ edge)؛ ) $ vertices \u003d array_unique ($ vertices)؛ foreach ($ vertices به عنوان $ vertex) ($ dist [$ vertex] \u003d INF؛ $ قبلی [$ vertex] \u003d NULL؛) $ dist [$ منبع] \u003d 0؛ $ Q \u003d $ vertices؛ در حالی که (شمارش ($ Q)\u003e 0) (// TODO - راه سریعتر برای بدست آوردن حداقل $ min \u003d INF را پیدا کنید ؛ پیشگویی ($ Q به عنوان $ vertex) (اگر ($ dist [$ vertex])< $min) { $min = $dist[$vertex]; $u = $vertex; } } $Q = array_diff($Q, array($u)); if ($dist[$u] == INF or $u == $target) { break; } if (isset($neighbours[$u])) { foreach ($neighbours[$u] as $arr) { $alt = $dist[$u] + $arr["cost"]; if ($alt < $dist[$arr["end"]]) { $dist[$arr["end"]] = $alt; $previous[$arr["end"]] = $u; } } } } $path = array(); $u = $target; while (isset($previous[$u])) { array_unshift($path, $u); $u = $previous[$u]; } array_unshift($path, $u); return $path; } $graph_array = array(array("a", "b", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path = dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n";

پایتون

از واردات مجموعه namestuple ، صف از واردات pprint pprint به عنوان pp inf \u003d float ("inf") Edge \u003d namestuple ("Edge" ، "شروع ، پایان ، هزینه") کلاس نمودار (): def __init __ (خود ، لبه ها): self .edges \u003d edge2 \u003d self.vertices \u003d set (sum ((برای e در edge2) ،))) def dijkstra (خود ، منبع ، مقصد): منبع را در self.vertices dist \u003d (vertex: inf for vertex in self.vertices ) previous \u003d (vertex: هیچکدام برای vertex در self.vertices) dist \u003d 0 q \u003d self.vertices.copy () همسایگان \u003d (vertex: set () برای vertex در self.vertices) برای شروع ، پایان ، هزینه در خود. لبه ها: همسایگان. ((پایان ، هزینه)) \u003d dest: break for v، هزینه در همسایگان [u]: alt \u003d dist [u] + هزینه اگر alt< dist[v]: # Relax (u,v,a) dist[v] = alt previous[v] = u #pp(previous) s, u = deque(), dest while previous[u]: s.pushleft(u) u = previous[u] s.pushleft(u) return s graph = Graph([("a", "b", 7), ("a", "c", 9), ("a", "f", 14), ("b", "c", 10), ("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6), ("e", "f", 9)]) pp(graph.dijkstra("a", "e")) Output: ["a", "c", "d", "e"]

از میان بسیاری از الگوریتم ها برای یافتن کوتاهترین مسیرها در یک نمودار ، در Habr فقط توضیحی از الگوریتم Floyd-Warshall پیدا کردم. این الگوریتم کوتاهترین مسیرها را بین همه راسهای نمودار و طول آنها پیدا می کند. در این مقاله ، اصل کارکرد الگوریتم Dijkstra را شرح می دهم ، که مسیرهای بهینه و طول آنها را بین یک راس خاص (منبع) و تمام رئوسهای دیگر نمودار پیدا می کند. ضرر این الگوریتم این است که اگر نمودار دارای قوسهای وزن منفی باشد ، به درستی کار نخواهد کرد.

به عنوان مثال ، نمودار گرا گرا را در نظر بگیرید:

ما می توانیم این نمودار را به صورت ماتریس C نمایان کنیم:

به عنوان یک منبع vertex 1 را بدست آورید.این بدان معنی است که ما کوتاهترین مسیرها را از راس 1 تا vertices 2 ، 3 ، 4 و 5 جستجو خواهیم کرد.
این الگوریتم قدم به قدم در تمام محورهای نمودار تکرار می شود و برچسب هایی را به آنها اختصاص می دهد ، که حداقل فاصله شناخته شده از راس منبع تا یک راس خاص است. این الگوریتم را به عنوان نمونه در نظر بگیرید.

برچسب 1 را به یک برچسب برابر با 0 اختصاص دهید ، زیرا این راس منبع است. راس های باقیمانده به برچسب هایی برابر با بی نهایت اختصاص می یابد.

بعد ، ما یک راس W انتخاب می کنیم که دارای برچسب حداقل باشد (اکنون آن راس 1 است) و تمام راسهایی را که از راس W در آن وجود دارد مسیری را در نظر می گیریم که شامل راس های واسطه ای نباشد. ما به هر یک از رئوس های در نظر گرفته شده برابر با برچسب W و طول مسیر از W تا راس مورد نظر یک برچسب اختصاص می دهیم ، اما فقط درصورتی که مبلغ بدست آمده از مقدار برچسب قبلی کمتر باشد. اگر مبلغ کمتر نیست ، برچسب قبلی را بدون تغییر بگذارید.

بعد از اینکه کلیه راسهایی را که مسیری مستقیم از W در آن وجود دارد بررسی کردیم ، راس W را به عنوان بازدید علامت گذاری می کنیم ، و یکی از کسانی که هنوز بازدید نشده را انتخاب کنید که دارای حداقل مقدار برچسب باشد ، راس بعدی W خواهد بود. در این حالت ، این vertex 2 است. یا 5. اگر چندین برآمدگی با همان برچسب ها وجود دارد ، فرقی نمی کند کدام یک را به عنوان W انتخاب کنیم.

ما راس 2. را انتخاب خواهیم کرد. اما هیچ مسیر خروجی واحدی از آن وجود ندارد ، بنابراین ما فوراً این راس را به عنوان بازدید علامت گذاری می کنیم و با حداقل علامت به سمت راس بعدی حرکت می کنیم. این بار فقط vertex 5 دارای برچسب حداقل است. تمام قله هایی که در آنها خطوط مستقیم 5 وجود دارد را در نظر بگیرید ، اما هنوز هم به عنوان بازدید مشخص نشده اند. باز هم مقدار برچسب راس W و وزن لبه را از W تا راس فعلی می یابیم و اگر این مبلغ از برچسب قبلی کمتر باشد ، مقدار علامت برچسب را با مبلغ دریافتی جایگزین می کنیم.

براساس تصویر ، می توانیم ببینیم که برچسب های قله های 3 و 4 کوچکتر شده اند ، یعنی مسیری کوتاه تر از این قله ها از بالای منبع پیدا شده است. در مرحله بعد ، راس 5 را به عنوان بازدید علامت بزنید و راس بعدی را که حداقل یک برچسب دارد انتخاب کنید. ما تمام اقدامات فوق را تکرار می کنیم تا زمانی که قله های بدون نظارت وجود نداشته باشد.

پس از انجام تمام اقدامات ، نتیجه زیر را می گیریم:

همچنین یک بردار P وجود دارد که از آن می توان کوتاهترین مسیرها را ساخت. با توجه به تعداد عناصر ، این بردار برابر با تعداد راسهای موجود در نمودار است.هر عنصر شامل آخرین راس میانی در کوتاهترین مسیر بین راس منبع و راس نهایی است. در ابتدای الگوریتم ، تمام عناصر بردار P برابر با راس منبع هستند (در مورد ما ، P \u003d (1 ، 1 ، 1 ، 1 ، 1)). در مرحله بعد ، در مرحله محاسبه مجدد مقدار برچسب برای راس مورد نظر ، اگر برچسب راس مورد نظر به كوچكتر تغییر یابد ، مقدار vertex فعلی W را به آرایه P. می نویسیم. علاوه بر این ، در W \u003d 5 ، برچسب راس 3 به "20" تغییر یافته است ، بنابراین مقدار را در بردار P - P \u003d 5 خواهیم نوشت. همچنین در W \u003d 5 ، مقدار برچسب در راس 4 تغییر یافت ("50" بود ، "40" شد) ، بنابراین باید مقدار W را به عنصر 4 بردار P - P \u003d 5 اختصاص دهید. در نتیجه ، بردار P \u003d (1 ، 1 ، 5 ، 5 ، 1) بدست می آوریم.

با دانستن اینکه در هر عنصر بردار P آخرین راس میانی در مسیر بین منبع و راس نهایی ثبت می شود ، می توانیم خود کوتاهترین مسیر را بدست آوریم.

کوتاهترین مسیر امروزه این یک کار حیاتی است و تقریباً در همه جا مورد استفاده قرار می گیرد ، از پیدا کردن مسیر بهینه بین دو شیء روی زمین (به عنوان مثال کوتاهترین مسیر از خانه به دانشگاه) ، در سیستم های اتوماتیک ، برای یافتن مسیر مطلوب برای حمل و نقل ، تعویض بسته اطلاعات در شبکه ها و و غیره.

کوتاهترین مسیر با کمک برخی از شیء ریاضی به نام نمودار بررسی می شود. جستجو کردن کوتاهترین مسیر بین دو راس داده شده در نمودار کشیده شده است. نتیجه یک مسیر است ، یعنی دنباله ای از رئوس و لبه های حادثه به دو راس مجاور و طول آن.

سه مورد را بیشتر در نظر بگیرید الگوریتم کارآمد یافته کوتاهترین مسیر:

الگوریتم Dijkstra;
الگوریتم فلوید؛
الگوریتم های جستجو

این الگوریتم ها با تعداد کمی از رئوس در نمودار به راحتی اجرا می شوند. با افزایش تعداد آنها ، کار جستجو کوتاهترین مسیر بغرنج.

الگوریتم Dijkstra

این الگوریتم یک الگوریتم نمودار است ، که توسط دانشمند هلندی E. Dijkstroy در سال 1959 اختراع شد. این الگوریتم کمترین فاصله را از یکی از راس نمودار نسبت به سایرین پیدا می کند و فقط برای نمودارهای بدون لبه های وزن منفی کار می کند.

وزن به هر راس اختصاص داده می شود - این وزن مسیر از راس اولیه به داده معین است. هر راس نیز می تواند انتخاب شود. اگر یک راس انتخاب شود ، آنگاه مسیر از آن به سمت راس اولیه کوتاهترین است ، در غیر این صورت ، موقتی است. با دور زدن نمودار ، الگوریتم مسیری را برای هر راس در نظر می گیرد و اگر کوتاه ترین باشد ، راس را انتخاب می کند. وزن این راس به وزن مسیر تبدیل می شود. برای همه همسایگان یک راس مشخص ، الگوریتم نیز وزن را محاسبه می کند ، در حالی که تحت هیچ شرایطی آنها را برجسته نمی کند. این الگوریتم کار خود را تمام می کند ، به اوج نهایی می رسد و وزن می کند کوتاهترین مسیر وزن راس نهایی می شود.

الگوریتم Dijkstra

مرحله 1. به تمام رئوس ها به جز اولین ، وزنی برابر با بی نهایت اختصاص داده می شود ، و اولین راس 0 قرار می گیرد.

مرحله 2. کلیه رئوس انتخاب نشده است.

مرحله 3. اولین راس جریان جاری است.

مرحله 4: وزن کلیه راسهای انتخاب نشده طبق فرمول محاسبه می شود: وزن یک راس انتخاب نشده حداقل عدد از وزن قدیمی یک راس داده شده ، جمع وزن وزنه راس جریان و وزن لبه اتصال راس جریان با غیر انتخابی است.

مرحله 5. در میان راس های انتخاب نشده ، راس با حداقل وزن جستجو می شود. اگر کسی پیدا نشود ، یعنی وزن همه راسها بی نهایت است ، پس مسیر وجود ندارد. بنابراین ، راه بیرون. در غیر این صورت ، راس یافت شده جریان می یابد. او ایستاده است.

مرحله 6. اگر راس فعلی محدود باشد ، در این صورت مسیر پیدا می شود ، و وزن آن وزن راس نهایی است.

مرحله 7. به مرحله 4 بروید.

در اجرای نرم افزار الگوریتم های Dijkstra ما مجموعه ای از راس S را ساختیم که کوتاهترین مسیرها از راس اولیه در حال حاضر شناخته شده است. در هر مرحله ، یکی از رئوس های باقیمانده به مجموعه S اضافه می شود ، فاصله آن از راس اولیه نسبت به دیگر راس های باقیمانده کمتر است. در این حالت از آرایه D استفاده خواهیم کرد که در آن طول ها نوشته شده است کوتاهترین مسیرها برای هر راس. هنگامی که مجموعه S شامل تمام عمودهای نمودار باشد ، آنگاه آرایه D شامل طولها خواهد بود کوتاهترین مسیرها از راس اولیه به هر راس.

علاوه بر این آرایه ها ، ما از یک ماتریس به طول C استفاده خواهیم کرد ، جایی که عنصر C طول لبه (i ، j) باشد ، اگر لبه ای در آن نباشد ، در این صورت طول آن بینهایت فرض می شود ، یعنی بیش از هر طول واقعی لبه ها. در حقیقت ، ماتریس C است ماتریس مجاورکه در آن تمام عناصر صفر با بی نهایت جایگزین می شوند.

برای تعیین خیلی

در پایان مسابقات عید نوروز ، حامی تصمیم گرفت از طریق نامه هدیه به برندگان جوایز بفرستد. با دانستن تعداد شرکت کنندگان $ n $ و زمان تحویل نامه بین برخی از بخش های Ukrposhta ، پس از حداقل زمان آخرین برندگان جایزه خود را دریافت کنید.

داده های ورودی

خط اول شامل شماره 3 $ $ است: تعداد شرکت کنندگان در مسابقات مسابقات $ n $ ، تعداد جایزه های حامی مالی $ M $ و تعداد زمان تحویل شناخته شده بین برخی از بخش ها $ k $ $. خط بعدی حاوی فضایی بین تعداد شرکت کنندگان که برنده شدند.

خط بعدی $ k $ 3 عدد 3 $ که هرکدام دارای اطلاعاتی در مورد زمان تحویل شناخته شده بین برخی از شعب در قالب هستند: $ a $ b $ $ t $ $ ، جایی که $ a $ و $ b $ تعداد شعب ، $ t $ $ (0 \\ leqslant t \\ leqslant 365) $ - زمان تحویل نامه پست بین آنها. آخرین خط شامل یک شماره واحد است - شماره اداره پست که از آن حامی مالی جوایز می فرستد. شناخته شده است که $ 1 \\ leqslant n ، m، a، b \\ leqslant 365 $.

خروجی

اگر همه جوایز به شرکت کنندگان تحویل داده شد ، "حامی خوب!" را در سطر اول و در ردیف بعدی چاپ کنید ، زمانی که آخرین نفر از برندگان جایزه خود را دریافت می کنند. اگر حداقل یکی از شرکت کنندگان نتواند جایزه دریافت کند ، در تنها خط "این مقصر حامی نیست ..." است. چاپ عبارات بدون نقل قول.

آزمایشات

№	داده های ورودی	خروجی
1.	3 2 2 2 3 1 2 3 2 3 4 1	حامی خوب! 7
2.	5 1 4 5 1 3 2 2 3 3 4 2 5 4 5 6 1	حامی خوب! 16
3.	7 2 6 1 3 1 3 2 2 4 32 4 5 94 3 1 0 6 2 4 7 2 3 7	این تقصیر اسپانسر نیست ...
4.	5 2 6 1 2 3 1 1 3 4 2 2 4 3 5 1 4 4 5 5 2 3 7 2	حامی خوب! 6