الگوریتم مقیاس‌دهی گبو برای کوتاه‌ترین مسیرها از یک مبدأ واحد

الگوریتم مقیاس دهی گبو برای کوتاهترین مسیرها از یک مبدأ واحد
(به انگلیسی: (Gabow's algorithm (single-source shortest paths) الگوریتم مقیاس دهی ابتدا با در نظر گرفتن فقط بالاترین بیت یک مقدار ورودی مناسب (مانند وزن یال‌ها)، مسئله را حل می‌کند. سپس جواب اولیه را با نگاه کردن به دو بیت اول پالایش می‌کند. به همین ترتیب بیت‌های بیشتر و بیشتری را در نظر می‌گیرد و در هر بار جواب را پالایش می‌کند تا این که همه بیت‌ها در نظر گرفته شوند و جواب صحیح محاسبه شود. دراین مسئله، الگوریتم محاسبه کوتاهترین مسیرها از یک مبدأ واحد را به وسیله مقیاس دهی وزن یال‌ها بررسی می‌کنیم. گراف جهت دار $G=(V,E)$ با وزن‌های صحیح غیر منفی $w$ داده شده‌است. فرض کنید $W=max_{(u,v)}\in E{w(u,v)}$ هدف، ایجاد الگوریتمی است که در زمان $O(ElgW)$ اجرا می‌شود. فرض می‌کنیم که همه راس‌ها از مبدأ قابل دستیابی‌اند. الگوریتم در نمایش دودویی وزن‌های یال‌ها، هربار یک بیت را به ترتیب با ارزش‌ترین بیت، وارد حل مسئله می‌کند. به ویژه فرض کنید $k=[lg(W+1)]+1$، تعداد بیت‌ها در نمایش دودویی $W$ باشد و برای $i=1,2,...,k$ $w_{i}(u,v)=[w(u,v)/2^{k-i}]$. به عبارت دیگر، $w_{i}(u,v)$ شکل "کوچک شده " $w(u,v)$است که به وسیله با ارزش‌ترین $i$ بیت، $w(u,v)$ تولید می‌شود. (بنابراین برای همه$(u,v)\in E$ داریم، $w_{k}(u,v)=w(u,v)$. بعنوان مثال اگر $k=5$ و$w(u,v)=<00100>=4$باشد آنگاه $w_{3}(u,v)=<001>=1$ است. $A_{i}(u,v)$ را به عنوان وزن کوتاهترین مسیر از راس $u$ به راس $v$ با استفاده از تابع وزن $w_{i}$ تعریف می‌کنیم؛ بنابراین برای همه $u,v\in V$ داریم $A_{k}(u,v)=A(u,v)$. برای مبدأ $s$الگوریتم مقیاس دهی ابتدا وزنهای کوتاهترین مسیر $A_{1}(u,v)$ را برای همه $v\in V$. محاسبه می‌کند، سپس برای همه $v\in V$ و$A_{2}(u,v)$. را محاسبه می‌کند و به همین ترتیب ادامه می‌دهد تا این که برای همه δ_k (u_,v)v∈V محاسبه شود. فرض می‌کنیم $|E|>=|V-1|$ است و خواهیم دید که محاسبه $A_{i}$ به اندازه $O(E)$، و لذا کل الگوریتم به اندازه $O(kE)=O(ElgW)$ زمان می‌برد.

مراحل

• فرض کنید برای همه راس‌های $v\in V$ داریم$A(s,v)<=|E|$ نشان دهید برای همه می‌توانیم $A(s,v)$ را در زمان $O(E)$ محاسبه کنیم.
• نشان دهید برای همه$v\in V$ می‌توانیم $A_{1}(s,v)$ را در زمان $O(E)$ محاسبه کنیم.
  

اکنون به محاسبه $A_{i}$ از $A_{i-1}$ می‌پردازیم.

• ثابت کنید برای هر $i=2,3,....,k$ داریم $w_{i}(u,v)=2w_{i-1}(u,v)+1$ یا $w_{i}(u,v)=2w_{i-1}(u,v)$.

سپس ثابت کنید که برای همه $v\in V$ داریم $2A_{i-1}(s,v)<=A_{i}(s,v)<=2A_{i-1}(s,v)+|V|-1$

• برای $i=2,3,...,k$ و $(u,v)\in E$ تعریف زیر را داریم
  

$check{w_{i}}(u,v)=w_{i}(u,v)+2A_{i-1}(s,u)-2A_{i-1}(s,v)$ ثابت کنید برای $i=2,3,...,k$ و همه$u,v\in V$, $check{w_{i}}(u,v)$ یال $(u,v)$ یعنی مقدار وزن جدید آن یال، یک عدد صحیح غیر منفی است.

• اینک ${A_{i}}(s,v)$ را به عنوان وزن کوتاهترین مسیر از $s$ به $v$ با استفاده از تابع وزن $check{w_{i}}$ تعریف می‌کنیم. ثابت کنید برای $i=2,3,...,k$ و همه $v\in V$ داریم

$A_{i}(s,v)=check{A_{i}}(s,v)+2A_{i-1}(s,v)$

و

$check{A_{i}}(s,v)<=|E|$

• نشان دهید چگونه برای همه$v\in V$ می‌توان $A_{i}(s,v)$ را از $A_{i-1}(s,v)$ در زمان $O(E)$ به دست آورد و نتیجه بگیرید که برای همه $A(s,v)$ , $O(E)$ می‌تواند در زمان $O(ElgW)$ محاسبه گردد.

منابع

• کتاب مقدمه‌ای بر الگوریتمها؛ فصل ۲۵ کرمن، لیزرسان، رایوست، استاین
• مقاله ی الگوریتم گبو در IEEE

پیوند به بیرون

• scaling algorithms(الگوریتم‌های پیدا کردن کوتاه‌ترین مسیر)