stanford-oval/wikipedia huggingface dataset:
مسیریابی (الگوریتم)
الگوریتم > الگوریتم Dijkstra

مقالهٔ اصلی: الگوریتم دایکسترا
الگوریتم Dijkstra برای یافتن کوتاهترین مسیر بین گره‌ها در یک گراف مورد استفاده قرار می‌گیرد. این الگوریتم به عنوان مثال، در شبکه‌های جاده‌ای کاربرد زیادی دارد. این الگوریتم توسط ادسخر دایکسترا در سال ۱۹۵۶ پیشنهاد شد.
این الگوریتم انواع مختلفی دارد. الگوریتم اصلی دایکسترا کوتاه‌ترین مسیر را بین دو گره معین پیدا می‌کرد، اما یک نوع رایج‌تر این الگوریتم یک گره منفرد را به عنوان گره "مبدأ" مشخص می‌کند و کوتاه‌ترین مسیر را از مبدأ مشخص شده تا همهٔ گره‌های دیگر در گراف پیدا می‌کند که به آن "درخت کوتاه‌ترین مسیر (Shortest path tree)" گفته می‌شود.
برای یک مبدأ مشخص شده در گراف، این الگوریتم کوتاه‌ترین مسیر را بین آن گره و سایر نقاط پیدا می‌کند. همچنین از این الگوریتم می‌توان برای یافتن کوتاه‌ترین مسیر بین دو گره مشخص استفاده کرد، به این صورت که الگوریتم از گره مبدأ آغاز می‌شود و در زمانی که به گره مقصد رسید متوقف خواهد شد. این الگوریتم کوتاه‌ترین مسیر به شکل گسترده در پروتکل‌های مسیریابی در شبکه‌ها کامپیوتری، به‌طور مثال در IS-IS یا در OSPF مورد استفاده است.
الگوریتم دایکسترا از برچسب‌هایی استفاده می‌کند که اعداد صحیح مثبت یا اعداد حقیقی هستند و کاملاً مرتب شده‌اند. اما می‌توان آن را به اعدادی که به صورت جزئی (محلی) مرتب هستند نیز تعمیم داد. به این عمومی سازی، الگوریتم کوتاه‌ترین مسیر عمومی دایکسترا گفته می‌شود.
الگوریتم دایکسترا برای ذخیره‌سازی دسترسی به اطلاعات ذخیره‌شده، از یک داده ساختار استفاده می‌کند. الگوریتم اصلی از صف اولویت‌دار استفاده می‌کند و پیچیدگی آن  O(|V|^{2}) (جایی که  |V| تعداد گره‌ها است) می‌باشد. ایده این الگوریتم در مقالهٔ (Leyzorek و دیگران 1957) نیز ارائه شده‌است. (Fredman و Tarjan 1984) با استفاده از یک صف اولویت‌دار در هرم فیبوناچی پیچیدگی زمان اجرا را به  O(|E|+|V|\log |V|) (که  |E| تعداد لبه‌ها است) رساندند. این الگوریتم به صورت مجانبی سریعترین الگوریتم یافتن کوتاه‌ترین مسیر از یک مبدأ برای یک گراف جهت دار با وزنهای غیر منفی بدون محدودیت شناخته شده‌است.
الگوریتم > الگوریتم Dijkstra > الگوریتم

گرهی که الگوریتم از آن آغاز می‌شود گره اولیه نامیده می‌شود. طول مسیر گره Y را فاصلهٔ گره Y تا گره اولیه (مبدأ) قرار می‌دهیم. الگوریتم دایکسترا مقادیر اولیه‌ای (معمولا صفر برای گره اولیه و بی‌نهایت برای سایر گره‌ها) را به گره‌ها نسبت می‌دهد و در هر مرحله آن را بهبود می‌بخشد.
در ابتدا همهٔ گره‌ها را «بازدیدنشده» نشانه‌گذاری می‌کنیم. سپس مجموعه‌ای از همهٔ گره‌های بازدید نشده می‌سازیم و آن را مجموعه «بازدیدنشده» نام‌گذاری می‌کنیم.
به هر گره یک مقدار فاصله آزمایشی اختصاص می‌دهیم. آن را برای گره اولیه صفر و برای تمام گره‌های دیگر بی‌نهایت قرار می‌دهیم. گره اولیه را به عنوان گره فعلی در نظر می‌گیریم.
برای گره فعلی، همهٔ گره‌های بازدید نشدهٔ همسایهٔ آن را در نظر می‌گیریم و فاصلهٔ آن‌ها را از گره فعلی حساب می‌کنیم. فاصلهٔ تازه محاسبه شده را با مقدار تعیین شدهٔ فعلی مقایسه می‌کنیم و کوچک‌ترین آن‌ها را به آن گره اختصاص می‌دهیم. به عنوان مثال، اگر گره فعلی A با فاصلهٔ 6 علامت‌گذاری شود و یالی که آن را به B متصل می‌کند دارای طول 2 باشد، در این صورت فاصله تا B از A برابر 6 + 2 = 8 خواهد بود. اگر قبلاً B با مسافت بیشتر از 8 مشخص شده بود، آن را به 8 تغییر می‌دهیم. در غیر این صورت، مقدار فعلی حفظ خواهد شد.
وقتی همهٔ همسایگان گره فعلی که «دیده‌نشده» نشانه‌گذاری شده بودند را پیمایش کردیم و به آنها یک فاصله اختصاص دادیم، گره فعلی را «بازدیدشده» علامت‌گذاری می‌کنیم و آن را از مجموعه «بازدیدنشده» خارج می‌کنیم. گره بازدیدشده هرگز دوباره بررسی نمی‌شود.
اگر گره مقصد مورد بازدید قرار گرفته شده باشد (هنگام پیدا کردن مسیری بین دو گره خاص) یا اگر کوچک‌ترین فاصله در بین گره‌های موجود در مجموعهٔ بازدیدنشده بی‌نهایت باشد (هنگام پیدا کردن یک گذر کامل؛ وقتی اتفاق می‌افتد که هیچ ارتباطی بین آن گره‌ها و گره اولیه وجود ندارد و گره‌ها بازدیدنشده باقی می‌مانند)، دیگر الگوریتم را ادامه نمی‌دهیم. الگوریتم به پایان رسیده‌است.
در غیر این صورت، گره بازدیدنشده را که با کم‌ترین فاصله مشخص شده‌است، انتخاب می‌کنیم، آن را به عنوان «گره فعلی» جدید تنظیم می‌کنیم و به مرحله 3 برمی‌گردیم.
هنگام پیدا کردن یک مسیر، لازم نیست صبر کنیم تا گره مقصد مانند «فوق» بازدید شود: الگوریتم می‌تواند هنگامی که گره مقصد کم‌ترین فاصله را بین همهٔ گره‌های «بازدیدنشده» داشته باشد متوقف شود (و بنابراین این گره می‌تواند به عنوان گره «فعلی» بعد از گره مبدأ مورد استفاده قرار گیرد).
الگوریتم > الگوریتم Dijkstra > شرح اجرا

فرض کنید می‌خواهیم کوتاه‌ترین مسیر بین دو نقطه روی نقشه را پیدا کنیم، یکی از این دو نقطه را نقطهٔ شروع و دیگری را به عنوان مقصد در نظر می‌گیریم. الگوریتم دایکسترا در ابتدا فاصلهٔ هر نقطهٔ تقاطع تا مبدأ روی نقشه را با بی‌نهایت نشانه گذاری می‌کند. این کار به این معنی نیست که فاصله‌ها بی‌نهایت هستند، بلکه به این معنا است که این نقاط تقاطع هنوز بازدید نشده‌اند (روش‌هایی نیز وجود دارند که تقاطع‌های بازدید نشده را در ابتدا نشانه گذاری نمی‌کنند). اکنون در هر تکرار یکی از این نقاط تقاطع را انتخاب می‌کنیم. در اولین مرحله، تقاطع فعلی، نقطهٔ شروع بوده و فاصله تا آن صفر خواهد بود (پس این نقطه را با صفر نشانه‌گذاری می‌کنیم). در مراحل بعد، نقطه‌ای که روی آن قرار داریم نزدیک‌ترین نقطه به مبدأ خواهد بود (پیدا کردن آن نیز کاری آسان خواهد بود).
از تقاطع فعلی، فاصلهٔ تمام نقاط تقاطعی که به آن به‌طور مستقیم متصل هستند و بازدید نشده‌اند را به‌روزرسانی می‌کنیم. این کار را به این صورت انجام می‌دهیم که مجموع فاصلهٔ نقطهٔ تقاطع مورد نظر با تقاطع فعلی را با نشانه‌ای که برای تقاطع فعلی در نظر گرفته‌ایم حساب می‌کنیم، پس از آن اگر مجموع حساب‌شده از نشانهٔ آن تقاطع بازدیدنشده کمتر بود آن را با مقدار جدید نشانه‌گذاری می‌کنیم. بعد از اینکه مسافت‌ها را برای هر تقاطع همسایه به‌روزرسانی کردیم، تقاطع فعلی را به عنوان بازدیدشده علامت‌گذاری می‌کنیم و یک تقاطع بازدید نشده با حداقل فاصله (از نقطهٔ شروع) -یا کمترین عدد نشانه‌گذاری شده روی آن- را به عنوان تقاطع فعلی انتخاب می‌کنیم. تقاطع‌هایی که به عنوان بازدیدشده هستند با کوتاه‌ترین مسیر از نقطهٔ مبدأ تا آن برچسب خورده‌اند و قابل بازنگری یا بازگشت به آن نخواهند بود.
این روند یعنی به روز رسانی تقاطع‌های همسایه با کمترین فاصلهٔ آن‌ها تا مبدأ، نشانه‌گذاری تقاطعی که روی آن بودیم به عنوان بازدیدشده و سپس انتخاب نزدیک‌ترین تقاطع همسایه به عنوان تقاطع بعدی را ادامه می‌دهیم تا زمانی که نقطهٔ مقصد مورد نظر را به عنوان بازدیدشده مشخص کنیم. هنگامی که مقصد را به عنوان بازدیدشده مشخص کردیم کوتاه‌ترین مسیر از نقطهٔ مبدأ تا آن را تعیین کرده‌ایم و می‌توانیم مسیر خود را به عقب با دنبال کردن جهت معکوس پیکان‌ها ردیابی کنیم. در اجرای الگوریتم، این کار معمولاً بدین صورت انجام می‌شود که از نقطهٔ مقصد شروع به دنبال کردن والدین آن و پس از آن والدین نقطهٔ بعدی می‌کنیم تا به نقطهٔ مبدأ برسیم. به همین دلیل والدین هر گره را نیز در هر مرحله باید داشته باشیم و به‌روز کنیم.
این الگوریتم همان‌طور که انتظار می‌رود هیچ تلاشی برای «کاوش» مستقیم به سمت نقطهٔ مقصد انجام نمی‌دهد. در عوض، تنها نکتهٔ مورد نظر برای تعیین نقطهٔ تقاطع بعدی، فاصله آن از نقطهٔ شروع است. این نکته نیز ممکن است یکی از نقاط ضعف الگوریتم را نشان دهد، کندی نسبی آن در برخی توپولوژی‌ها.
الگوریتم > الگوریتم Dijkstra > شبه کد

در الگوریتم زیر، کد u ← vertex در Q با حداقل فاصله [u]، گره u را در مجموعه گره‌های Q جست و جو می‌کند که حداقل فاصلهٔ آن [dist[u است. (length(u, v فاصلهٔ بین دو گره همسایه u و v را برمی‌گرداند. متغیر alt در خط 18 طول مسیر از گره ریشه (نقطهٔ مبدأ) تا گره همسایه v است به طوری که این مسیر از گره u عبور کند. اگر این مسیر محاسبه شده کوتاه‌تر از کوتاه‌ترین مسیری باشد که برای v ثبت شده‌است، مسیر محاسبه‌شده در متغیر alt با مسیر قبلی جایگزین می‌شود. آرایه prev شامل اشاره‌گرها به گره بعدی است تا کوتاه‌ترین مسیر به مبدأ قابل بازیابی باشد.
1 function Dijkstra(Graph, source):
2
3       create vertex set Q
4
5       for each vertex v in Graph:
6           dist[v] ← INFINITY
7           prev[v] ← UNDEFINED
8           add v to Q
9       dist[source] ← 0
10
11      while Q is not empty:
12          u ← vertex in Q with min dist[u]
13
14          remove u from Q
15
16          for each neighbor v of u: // only v that are still in Q
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:
19              dist[v] ← alt
20              prev[v] ← u
21
22      return dist[], prev[]
در صورتی که فقط به کوتاه‌ترین مسیر بین گره مبدأ و مقصد علاقه‌مند باشیم، می‌توانیم جستجو را پس از خط 15 با این شرط که u = target خاتمه دهیم. اکنون می‌توانیم کوتاه‌ترین مسیر از مبدأ به مقصد را با یک تکرار معکوس به شکل زیر بخوانیم:
1 S ← empty sequence
2 u ← target
3 if prev[u] is defined or u = source: // Do something only if the vertex is reachable
4       while u is defined: // Construct the shortest path with a stack S
5           insert u at the beginning of S // Push the vertex onto the stack
6           u ← prev[u] // Traverse from target to source
حالا دنبالهٔ S لیستی از رئوسی است که یکی از کوتاه‌ترین مسیرها از مبدأ به مقصد را تشکیل می‌دهند. البته اگر هیچ مسیری وجود نداشته باشد، دنباله خالی خواهد بود.
یک مسئلهٔ کلی تر این است که همهٔ کوتاهترین مسیرها را بین مبدأ و مقصد پیدا کنیم (ممکن است چندین مسیر مختلف با طول یکسان وجود داشته باشد). در این صورت به جای این که فقط یک گره را هر بار در آرایه []prev ذخیره کنیم، تمام گره‌هایی که شرایط مورد نظر در الگوریتم را برآورده می‌سازد در آن ذخیره می‌کنیم. به عنوان مثال، اگر هم گره r و هم مبدأ، متصل به گره مقصد باشند و هر دوی آن‌ها شامل کوتاه‌ترین مسیرهای مختلف به گره مقصد باشند، هر دو را به آرایه [prev[target  اضافه می‌کنیم. وقتی که الگوریتم به پایان رسید، []prev در واقع یک ساختار داده خواهد بود که زیرمجموعه‌ای از گراف اصلی است به طوری که برخی از یال‌های آن برداشته شده‌است. ویژگی اصلی این ساختار داده این خواهد بود که اگر الگوریتم برای همهٔ گره‌ها به عنوان گره مبدأ اجرا شود، آنگاه هر مسیری از آن گره به هر گره دیگر در گراف جدید، کوتاه‌ترین مسیر بین آن گره‌ها در گراف اصلی خواهد بود، و تمام مسیرهایی از آن طول در گراف اصلی در گراف جدید نیز موجود است. سپس برای یافتن همه این کوتاه‌ترین مسیرها بین دو گره داده شده، از الگوریتمی برای یافتن مسیر در گراف جدید مانند جستجوی اول عمق استفاده خواهیم کرد.
الگوریتم > الگوریتم بلمن-فورد

مقالهٔ اصلی: الگوریتم بلمن-فورد
الگوریتم > الگوریتم بلمن-فورد > مقدمه

الگوریتم Bellman-Ford الگوریتمی برای پیدا کردن کوتاه‌ترین مسیر از یک راس گراف به عنوان منبع به کلیه راس‌های دیگر در یک گراف وزن‌دار است. این الگوریتم در حل یک مسئله مشخص از الگوریتم دکسترا کندتر است، اما برای حل مسائل بیشتری کاربرد دارد، زیرا این قابلیت را دارد که برای گراف‌هایی با وزن منفی نیز استفاده شود. این الگوریتم برای اولین بار توسط آلفونسو شیمبل ارائه شده‌است، اما به نام ریچارد بلمن و لستر فورد جونیور نامگذاری شده‌است که به ترتیب در سال ۱۹۵۸ و ۱۹۵۶ این الگوریتم را منتشر کردند. ادوارد اف. مور نیز در سال ۱۹۵۷ همین الگوریتم را منتشر کرد و به همین دلیل گاهی اوقات الگوریتم بلمن-فورد-مور نیز نامیده می‌شود.
یال‌های منفی گراف‌ها در بسیاری از مسائل کاربرد دارد، از این رو این الگوریتم می‌تواند از جهت کمک به حل این نوع از مسائل بسیار سودمند باشد.  اگر یک گراف شامل یک «دور منفی» (یعنی دوری که مجموع وزن یال‌های آن به یک مقدار منفی برسد) که از مبدأ قابل دسترسی باشد، کوتاهترین مسیر وجود ندارد: هر مسیری که دارای یک راس در دور منفی باشد می‌تواند با هر بار پیمایش دور منفی موجود در گراف به مسیر کوتاه تری تبدیل شود. در چنین حالتی، الگوریتم بلمن-فورد می‌تواند دور منفی را شناسایی و گزارش کند.
الگوریتم > الگوریتم بلمن-فورد > الگوریتم

مانند الگوریتم دایکسترا، بلمن-فورد با استفاده از روش «ریلکس» کردن (relaxation) پیش می‌رود، که در آن تقریب فاصلهٔ صحیح با فواصل بهتر در طول الگوریتم جایگزین می‌شود تا اینکه در نهایت به بهترین جواب برسد. در هر دو الگوریتم، فاصلهٔ تقریبی مبدأ با هر راس در گراف همیشه فراتر از فاصلهٔ واقعی است و در طول اجرا با حداقل مقدار از بین مقدار قدیمی آن و مسیر تازه پیدا شده جایگزین می‌شود. با این حال، الگوریتم دایکسترا از صف اولویت دار برای انتخاب حریصانه‌ی نزدیکترین راسی که هنوز پردازش نشده‌است استفاده می‌کند و همین روند را برای تمامی یال‌های خروجی راس‌ها انجام می‌دهد. در مقابل، الگوریتم بلمن-فورد به راحتی تمام یال‌ها را «ریلکس» می‌کند و ریلکس کردن را  |V|-1 بار انجام می‌دهد، که در آن  |V| تعداد راس‌های موجود در گراف است. در هر یک از این تکرارها تعداد راس‌ها با فاصلهٔ درست از مبدأ رشد می‌کند، که در نهایت منجر به این می‌شود که فاصله همه راس‌ها از مبدأ به‌طور صحیح محاسبه شود. این روش اجازه می‌دهد تا الگوریتم بلمن-فورد برای طیف گسترده‌تری از گراف‌ها به عنوان ورودی اجرا شود.
پیچیدگی زمانی اجرا ی الگوریتم بلمن - فورد  O(|V|\cdot |E|) است، که در آن  |V| و  |E| به ترتیب تعداد راس‌ها و یال‌های گراف هستند.
1function BellmanFord(list vertices, list edges, vertex source) is
2    ::distance[], predecessor[]
3
4    // This implementation takes in a graph, represented as
5    // lists of vertices and edges, and fills two arrays
6    // (distance and predecessor) about the shortest path
7    // from the source to each vertex
8    // Step 1: initialize graph
9    for each vertex v in vertices do
10        distance[v] := inf          // Initialize the distance to all vertices to infinity
11        predecessor[v] := null       // And having a null predecessor
12        distance[source] := 0           // The distance from the source to itself is, of course, zero
13
14
15    // Step 2: relax edges repeatedly
16
17    for i from 1 to size(vertices)−1 do         //just |V|−1 repetitions; i is never referenced
18        for each edge (u, v) with weight w in edges do
19            if distance[u] + w < distance[v] then
20                distance[v] := distance[u] + w
21                predecessor[v] := u
22
23
24    // Step 3: check for negative-weight cycles
25
26    for each edge (u, v) with weight w in edges do
27        if distance[u] + w < distance[v] then
28            error "Graph contains a negative-weight cycle"
29
30
31    return distance[], predecessor[]
به عبارت ساده، این الگوریتم در ابتدای کار فاصلهٔ مبدأ را برابر صفر و همه راس‌های دیگر گراف را بی‌نهایت قرار می‌دهد. سپس برای همه یال‌ها، اگر با در نظر گرفتن آن یال فاصلهٔ مقصد کاهش پیدا کند، فاصله به مقدار کمتر جدید به روز می‌شود. در i‌اُمین بار تکرار الگوریتم که یال‌ها مورد بررسی قرار می‌گیرند، این الگوریتم تمام مسیرهای با طول i یال (و احتمالاً برخی از مسیرهای طولانی‌تر از i یال) پیدا می‌کند. از آنجایی که طولانی‌ترین مسیر ممکن بدون دور می‌تواند شامل  |V|-1 یال باشد، یال‌ها باید  |V|-1 بار بررسی شوند تا مطمئن شویم که کوتاه‌ترین مسیر برای همه راس‌ها پیدا شده‌است. بررسی نهایی برای تمامی یال‌ها انجام می‌شود و اگر فاصله‌ای به روز شود، مسیری به طول  |V|یال پیدا شده‌است که تنها در صورت وجود حداقل یک دور با وزن منفی در گراف می‌تواند رخ دهد.
الگوریتم > الگوریتم *A

مقاله اصلی: الگوریتم *A
این الگوریتم در ابتدا توسط پیتر ای هارت (Peter E. Hart)، نیلز جان نیلسون (Nils John Nilsson) و برترام رافائل (Bertram Raphael) در سال ۱۹۶۸ میلادی ارائه و شرح داده شد. در واقع این الگوریتم ترکیبی از الگوریتم Dijkstra و الگوریتم جستجوی ابتدا-بهترینِ حریصانه است و در عین حال که کوتاه‌ترین مسیر را می‌یابد (البته در مواردی که خانه‌های بسته -خانه‌هایی که غیرقابل عبورند- وجود دارد این ویژگی تضمین شده نیست)، از هر دو سریعتر کار می‌کند.
در این الگوریتم، ابتدا دو لیست تعریف می‌کنیم؛ لیست باز (open list) و لیست بسته (closed list). سپس نقطه مبدأ را به لیست بسته اضافه می‌کنیم و در هر مرحله راس‌های قابل تردد همسایهٔ راس فعلی را به لیست باز اضافه می‌کنیم. حال باید دو تابع تعریف کنیم:
تابع G: هزینهٔ رسیدن تا مکان فعلی (مقدار یال‌های طی شده از مبدأ تا راس فعلی)
تابع H: هیوریستیک یا تخمین هزینهٔ رسیدن از راس فعلی تا مقصد
حال اگر تعریف کنیم: (F(node) = G(node) + H(node، آنگاه این تابع برآورد کم‌هزینه‌ترین مسیر از node به مقصد است. برای محاسبهٔ G مقدار G والد (آخرین راس قبل از راس فعلی که از آن گذشته‌ایم) آن راس را یک واحد بیشتر می‌کنیم. برای حساب کردن H راه‌های مختلفی وجود دارد مانند روش فاصلهٔ منهتن (Manhattan distance method)، روش فاصلهٔ قطری (Diagonal distance method)، روش فاصلهٔ اقلیدسی (Euclidean distance method) و …
این الگوریتم این گونه کار می‌کند که در هر مرحله به کم‌هزینه‌ترین راس موجود در لیست باز می‌رود و هر همسایه راس فعلی مانند T سه حالت دارد:
اگر T در لیست بسته بود، کاری نمی‌کند.
اگر T در لیست باز بود، با G و H جدید Fاش را به‌روزرسانی می‌کند.
اگر T در هیچ‌کدام نبود، به لیست باز اضافه شده و مقدار توابع G و H و Fاش محاسبه می‌شود.
شبه کد الگوریتم *A به صورت زیر است:
function A*(start, goal)
    closed = empty set
    q = makequeue(path(start))
    while q is not empty do
        p = removefirst(q)

        x = lastnode(p)

        if x in closed then
        end if

        if x = goal then
            return p
        end if

        add x to closed

        for y := successor(x) do
            enqueue(p,q,y)
        end for

        return Failure
    end while
end function
الگوریتم > الگوریتم نمونه

حال برای درک بهتر الگوریتم‌های مسیریابی می‌توان به مثال زیر توجه کرد. در نقشهٔ زیر x نماد مکان‌های بسته یا دیوار، s محل شروع، o نقطهٔ پایان و _ مکان‌های باز نقشه را نشان می‌دهند.
1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X 5
X _ X _ _ X _ X _ X 6
X _ X X _ _ _ X _ X 7
X _ _ O _ X _ _ _ X 8
X X X X X X X X X X
برای شروع به یک لیست از مختصات‌ها نیاز است که در این مورد از یک صف استفاده می‌شود. این صف ابتدا به وسیلهٔ مختصات نقطهٔ نهایی مقدار دهی اولیه می‌شود. همچنین به هر کدام از اعضای صف یک شمارنده تخصیص داده می‌شود. در مثال مورد بررسی، صف با ((۳٬۸٬۰)) شروع می‌شود.
سپس بر روی تمام اعضای صف پیمایش انجام می‌شود و اعمال زیر برای هر عضو انجام می‌شود.
یک لیست از چهار عنصر مجاور آن تشکیل داده می‌شود که یرای هر عنصر متغیر شمارندهٔ آن، شمارندهٔ عنصر در صف به علاوهٔ یک می‌باشد؛ که در مثال بالا این لیست به صورت ((۲٬۸٬۱),(۳٬۷٬۱),(۴٬۸٬۱),(۳٬۹٬۱)) است.
حال عناصر موجود در این لیست جدید بررسی می‌شود که اگر آن عنصر ذیوار بود یا در لیست اصلی مختصاتی مشابه با شمارندهٔ کمتر وجود داشت حذف می‌شود.
عناصر باقی‌مانده به صف اصلی اضافه می‌شوند.
عنصر بعدی بررسی می‌شود.
این کار را تا زمانی انجام می‌پذیرد که نقطهٔ شروع مشاهده شود. هنگامی که به نقطه شروع برسیم مشاهده می‌شود که نقاطی که در صف هستند، یک مقدار شمارنده به آنها تخصیص داده شده‌است. در نقشه زیر این موضوع مشخص است.
1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X 6 X 6 _ X _ _ _ X 4
X 5 6 5 X X 6 X _ X 5
X 4 X 4 3 X 5 X _ X 6
X 3 X X 2 3 4 X _ X 7
X 2 1 0 1 X 5 6 _ X 8
X X X X X X X X X X
حال از نقطهٔ S پیمایش شروع می‌شود و در هر مرحله از بین مختصات‌های مجاور هر نقطه، به نقطه ای با کمترین مقدار شمارنده حرکت می‌کنیم.
مقایسهٔ الگوریتم‌ها

در جدول زیر، الگوریتم‌های شاخص مسیریابی از جهت پیچیدگی زمانی و مورد کاربرد با یکدیگر مقایسه شده‌اند.
| الگوریتم | پیچیدگی زمانی | توضیحات |
| --- | --- | --- |
| جستجوی اول عمق |  O(V+E) | برای گراف‌های بدون وزن |
| جستجوی اول سطح |  O(V+E) | برای گراف‌های بدون وزن |
| دایکسترا |  O(VlogV+E) | برای گراف‌های وزن‌دار بدون دور منفی |
| بلمن-فورد |  O(VE) | برای گراف‌های وزن‌دار با قابلیت اعمال بر گراف‌های دارای دور منفی |
| *A |  O(E) | برای گراف‌های وزن‌دار بدون دور منفی |
کاربردهای مسیریابی

مسیریابی در شبکه‌های کامپیوتری: برای انتقال داده بین دو گره شبکه از الگوریتم‌های مسیریابی برای پیدا کردن بهترین مسیر بین دو گره استفاده می‌شود.
بازی‌های کامپیوتری: الگوریتم‌های مسیریابی در واقع هستهٔ هر سیستم حرکتی مجهز به هوش مصنوعی هستند. الگوریتم‌های مسیریابی در بازی‌های کامپیوتری وظیفه دارند تا بین هر دو نقطهٔ روی مختصات بازی بهترین مسیر را پیدا کنند.
نقشه‌های آنلاین: استفادهٔ این برنامه‌ها از مسیریابی در زندگی روزمره بسیار زیاد است. الگوریتم‌های مسیریابی باید بتوانند در هر زمانی با در نظر گرفتن متغیرهای مختلفی (اعم از ترافیک، مسیرهای مسدودشده و …) مسیرهای مناسب را به کاربران پیشنهاد دهند.
ساخت و ساز راه‌ها: یکی از کاربردهای مسیریابی پیدا کردن جاده‌ها است. این امر به این شکل انجام می‌گیرد که مسیرهای تصادفی بین مکان‌هایی که مردم علاقه زیادی به استفاده از آنها دارند انتخاب می‌شود. سپس با توجه به اینکه کدام مسیرها فضای بیشتری را روی نقشه پوشش می‌دهند، جاده‌ها روی آن‌ها بنا می‌شوند. از این الگوریتم برای ساختن انواع راه‌ها مانند بزرگراه‌ها، جاده‌های بین شهری، راه‌های خاکی و … استفاده می‌شود. یکی از مهم‌ترین کاربردهای این الگوریتم در ساختن جاده‌های کوهستانی است که برای پرهیز از شیب‌های تند استفاده می‌شود.
شهرسازی: مناطقی که محل تقاطع چند مسیر مختلف هستند محل مناسبی برای ساختن شهرها محسوب می‌شوند.
تجزیه و تحلیل زمین: با استفاده از همان رویکرد راه‌سازی، می‌توان از مسیریابی استفاده کرد تا مشخص شود که چه مناطقی احتمالاً بیشتر در مسیر رفت و آمد قرار دارند. این نقاط و مناطق نزدیک به آنها، از نظر استراتژیک دارای اهمیت هستند.
مکان یابی در محیط‌های رزمی: از همان روش بالا برای تجزیه و تحلیل زمین، با تجزیه و تحلیل بیشتر مسیر، می‌توانیم مکان‌هایی را در طول مسیر پیدا کنیم که برای دشمن تا N قدم بعدی در مسیر متنهی به آن قابل رویت نباشد. قرار دادن کمین در یکی از این نقاط بدان معنی است که دشمن تا زمانی که در فاصله N قرار نگیرید، شما را نمی‌بیند، بنابراین می‌توان با یک نیروی بزرگ کمین کرد.
رباتیک: از جمله مسائل مهم در ربات‌های متحرک مسیریابی می‌باشد که هوش مصنوعی به آن ورود کرده‌است. مریخ‌نوردها ربات‌هایی هستند که از الگوریتم‌های مسیریابی استفاده می‌کنند. مریخ‌نوردها از الگوریتم‌های مسیریابی استفاده می‌کنند.
جستجوی اول عمق یک راه‌حل سریع و مناسب برای پیداکردن مسیر در هزارتوهاست.
یک نمایش ترسیمی از الگوریتم جستجوی اول سطح. هدف یافتن کوتاه‌ترین مسیر از گره «آ» به گره «ح» است.
یک نمایش ترسمی از الگوریتم دایکسترا. هدف یافتن کوتاه‌ترین مسیر از گره «آ» به گره «ح» است.
یک نمایش ترسیمی از الگوریتم بلمن-فورد. هدف یافتن کوتاه‌ترین مسیر گره «آ» به گره «ت» است.
تلمبه ۲۰۶

| روستای امیرآباد | روستای امیرآباد |
| --- | --- |
روستا: روستا
کشور: ایران
استان: کرمان
شهرستان: بردسیر
بخش: بخش نگار
دهستان: نگار
جمعیت: ۶۸ نفر (سرشماری ۹۵)
روستای امیرآباد، یک منطقه مسکونی از توابع بخش نگار، حد فاصل نگار تا بهرامجرد نبش دکل مخابراتی از توابع شهرستان بردسیر در استان کرمان ایران است.این روستا شامل باغات سیاه درختی مانند ..میوه به و زردآلو و هلو و.... علوفه شامل یونجه و علف و همچنین بوم گردی بنام 206می‌باشد.
جمعیت

این روستا در دهستان نگار قرار دارد و براساس سرشماری مرکز آمار ایران در سال ۱۳۹۵، جمعیت آن ۶۸ نفر (۲۳ خانوار) بوده‌است.
حوزه انتخابیه قم، کهک و جعفرآباد

|  حوزه قم، کهک و جعفرآباد |  حوزه قم، کهک و جعفرآباد |
| --- | --- |
حوزهٔ انتخاباتی   مربوط به مجلس شورای اسلامی: حوزهٔ انتخاباتی   مربوط به مجلس شورای اسلامی
موقعیت حوزه در استان قم: موقعیت حوزه در استان قم
شهرستان(ها): قم، کهک و جعفرآباد
استان: قم
جمعیت: ۱٬۱۵۱٬۶۷۲
مقرهای کلان: قم (مرکز) کهک و جعفریه
حوزهٔ کنونی: حوزهٔ کنونی
شکل‌گیری: ۱۳۷۸
کرسی‌ها: ۳ از ۲۹۰ 
فهرست/ تشکل: فهرست جبههٔ متحد: ۱ فهرست پایداری: ۱ مشترک پایداری و متحد: ۱
نماینده(گان): مجتبی ذوالنوری محمد منان رئیسی قاسم روانبخش
بخش‌ها: مرکزی قم ، مرکزی جعفرآباد ، مرکزی کهک ، بخش خلجستان ، بخش سلفچگان ، بخش قاهان ، بخش فردو
شکل‌گیری از: قم (۱۳۶۶)
جناح: اصولگرایان
حوزه انتخابیه قم، کهک و جعفرآباد تنها حوزهٔ استان قم برای انتخابات مجلس شورای اسلامی است. این حوزه به مرکزیت شهر قم ۳ نماینده دارد.
علی لاریجانی رئیس مجلس‌های هشتم، نهم و دهم نمایندهٔ حوزهٔ قم و تنها رئیس مجلس از حوزه‌ای به جز تهران بود.
پیشینه

در جدول حوزه‌های انتخاباتی مصوبهٔ ۱۳۵۸ شورای انقلاب در حالی که شهر قم جزو استان مرکزی بود، بخش جعفرآباد جزو حوزهٔ ساوه بود و ساوه ۲ نماینده در مجلس داشت.
در سال ۱۳۶۶ که قم جزو استان تهران بود، بخش جعفرآباد به حوزهٔ قم بازگشت ولی بخش خلجستان در حوزهٔ تفرش قرار گرفت.
حوزهٔ قم در سال ۱۳۷۴ تغییر نکرد و در سال ۱۳۷۵ قم استان شد. تا اینکه در سال ۱۳۷۸ بخش خلجستان دوباره به قم بازگشت و نمایندگان حوزه به ۳ نفر افزایش یافت.
در سال ۱۳۸۱ نیز بخش سلفچگان تشکیل شد.
وضعیت فعلی

طبق تقسیمات کشوری کنونی وضعیت حوزه بدین شرح است:
| شهرستان | بخش‌ها | جمیعت (۱۳۹۵) |
| --- | --- | --- |
| قم | شهر قم (مرکز حوزه) ، بخش مرکزی ، بخش سلفچگان ، بخش خلجستان | ۱٬۲۰۱٬۱۵۸ |
| کهک | شهر کهک ، بخش مرکزی ، بخش فردو | ۱۷٬۱۰۶ |
| جعفرآباد | شهر جعفریه ، بخش مرکزی ، بخش قاهان | ۲۱٬۹۶۳ |
نمایندگان > مجلس نهم

در انتخابات مجلس نهم در سال ۱۳۹۰–۹۱ علی لاریجانی رئیس مجلس نهم از فهرست جبههٔ متحد اصولگرایان و یک نماینده از فهرست جبههٔ پایداری و یک نماینده از هردو فهرست به مجلس راه یافتند.
| نام | فهرست | گرایش (هنگام انتخابات) | تشکل سیاسی (هنگام انتخابات) | رأی |
| --- | --- | --- | --- | --- |
| علی لاریجانی | جبههٔ متحد اصولگرایان | اصولگرا | مستقل | ۲۷۰٬۳۸۲ |
| رضا آشتیانی عراقی | پایداری و متحد | اصولگرا | جامعهٔ مدرسین | ۱۶۴٬۲۱۹ |
| احمد امیرآبادی فراهانی | جبههٔ پایداری | اصولگرا | جبههٔ پایداری | ۱۴۷٬۷۶۵ |
| مجموع | مجموع | مجموع | مجموع | ۴۱۴٬۸۶۵ |
نمایندگان > مجلس دهم

در این دوره از انتخابات، علی لاریجانی که دو دوره قبل رای اول بود، نتوانست این رتبه را حفظ کند ولی نهایتا او به همراه امیرآبادی و ذوالنوری به مجلس راه یافت.
| نام | فهرست | گرایش (هنگام انتخابات) | تشکل سیاسی (هنگام انتخابات) | رأی |
| --- | --- | --- | --- | --- |
| احمد امیرآبادی فراهانی | جبههٔ پایداری | اصولگرا | جبههٔ پایداری | 263،885 |
| علی لاریجانی | ائتلاف فراگیر اصلاح‌طلبان: گام دوم | اصولگرا | مستقل | 191،329 |
| مجتبی ذوالنوری | جبههٔ پایداری | اصولگرا | جبههٔ پایداری | 168،397 |
| مجموع | مجموع | مجموع | مجموع | 443،797 |