• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

کوتاه ترین مسیر در گراف

  • شروع کننده موضوع
  • #1

armita

کاربر خاک‌انجمن‌خورده
ارسال‌ها
2,204
امتیاز
684
نام مرکز سمپاد
دبیرستان فرزانگان ۱
شهر
تهران
دانشگاه
شریف
رشته دانشگاه
‫علوم کامپیوتر‬‎
به نظرتون چجوری می شه کوتاه ترین فاصله ی بین دو راس در یک گراف رو حساب کرد ؟ (اگر جواب رو می دونید یه دفعه نگین که بقیه فکر کنند :D)
 

zabolian

کاربر نیمه‌حرفه‌ای
ارسال‌ها
235
امتیاز
25
نام مرکز سمپاد
دبیرستان شهید اژه ای اصفهان
شهر
اصفهان
سال فارغ التحصیلی
1390
مدال المپیاد
۳ روز پیش ( ۲۴ اسفند ۸۸) مدال طلای المپیاد کامپیوتر گرفتم
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی نرم افزار
پاسخ : کوتاه ترین مسیر در گراف

گراف وزن دار باشه یا بی وزن؟
الان سعی کردم یه دفعه نگم :D
 

trustme

لنگر انداخته
ارسال‌ها
2,810
امتیاز
893
نام مرکز سمپاد
شهید بهشتی
شهر
کاشان
سال فارغ التحصیلی
1387
دانشگاه
دانشگاه خواجه نصیر طوسی
رشته دانشگاه
مهندسی مکانیک
پاسخ : کوتاه ترین مسیر در گراف

خوب بهتر ه اول بی وزن رو بررسی کنیم ... بعد توی تصمیم گیری بررسی کنیم وزن دار چه فرقی با بی وزن داره :D

من یه نظر دارم ... هر راس با چند راس دیگه مجاور ه .. اینا رو مشخص می کنیم؛ بعد یه تابع بازگشتی بزاریم، بره تعداد راس هایی که به راس انتخاب شده وصل هستند رو پیدا کنه و چک کنه مسیر پیدا کرده یا نه، طول مسیر رو هم یکی اضافه کنه ... برای اینکه دور خودش بی خود چرخ نزنه، باید توی فرخواندن تابع، بررسی کنیم که آیا از اونجا رد شده یا نه.. ، اگه آره که برگرده یه مرحله بالاتر :D

اینطوری جواب می ده ؟!
 

zabolian

کاربر نیمه‌حرفه‌ای
ارسال‌ها
235
امتیاز
25
نام مرکز سمپاد
دبیرستان شهید اژه ای اصفهان
شهر
اصفهان
سال فارغ التحصیلی
1390
مدال المپیاد
۳ روز پیش ( ۲۴ اسفند ۸۸) مدال طلای المپیاد کامپیوتر گرفتم
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی نرم افزار
پاسخ : کوتاه ترین مسیر در گراف

تقریبا همینه، بدون تابع بازگشتی هم می شه راحت بیانش کرد، روش فکر کنید، قشنگه
 

zabolian

کاربر نیمه‌حرفه‌ای
ارسال‌ها
235
امتیاز
25
نام مرکز سمپاد
دبیرستان شهید اژه ای اصفهان
شهر
اصفهان
سال فارغ التحصیلی
1390
مدال المپیاد
۳ روز پیش ( ۲۴ اسفند ۸۸) مدال طلای المپیاد کامپیوتر گرفتم
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی نرم افزار
پاسخ : کوتاه ترین مسیر در گراف

اون قسمت بازگشتی رو می شه یه کم توضیح بدید، یعنی اگه رفت به یه همسایه و دید پیدا نکرده بعدش چی کار می کنه؟ یعنی دوباره برمیگرده راس پدر و کار رو ادامه می ده ( روی بقیه همسایه ها) یا اینکه این بار از این راس جدید دنبال مسیر میگرده؟
 

trustme

لنگر انداخته
ارسال‌ها
2,810
امتیاز
893
نام مرکز سمپاد
شهید بهشتی
شهر
کاشان
سال فارغ التحصیلی
1387
دانشگاه
دانشگاه خواجه نصیر طوسی
رشته دانشگاه
مهندسی مکانیک
پاسخ : کوتاه ترین مسیر در گراف

به نقل از محمد زابلیان :
اون قسمت بازگشتی رو می شه یه کم توضیح بدید، یعنی اگه رفت به یه همسایه و دید پیدا نکرده بعدش چی کار می کنه؟ یعنی دوباره برمیگرده راس پدر و کار رو ادامه می ده ( روی بقیه همسایه ها) یا اینکه این بار از این راس جدید دنبال مسیر میگرده؟
من اینطوری تصور کرده بودم: یه آرایه به اندازه تمامی راس ها داریم برای نگه داشتن راس هایی که رفتیم؛
هر راس جدید که انتخاب می شه، توی آرایه در آخرین خونه ریخته بشه؛ اگه جواب نداد اون راس، خوب پاکش می کنیم.
توی تابع هم بیاد آخرین راسی که رفته رو از آرایه بخونه؛ همه حالت های ممکن رو فرخوانی کنه (چقدر بهینه است واقعا :D)
... فکر می کنم اینطوری جواب می ده؛ هوم؟
 

zabolian

کاربر نیمه‌حرفه‌ای
ارسال‌ها
235
امتیاز
25
نام مرکز سمپاد
دبیرستان شهید اژه ای اصفهان
شهر
اصفهان
سال فارغ التحصیلی
1390
مدال المپیاد
۳ روز پیش ( ۲۴ اسفند ۸۸) مدال طلای المپیاد کامپیوتر گرفتم
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی نرم افزار
پاسخ : کوتاه ترین مسیر در گراف

اون قسمت که چک می کنید جواب میده یا نه چه جوریه؟
اگه منظور شما رو درست فهمیده باشم:
مثلا فرض کنید ۱ به ۲ و ۳ یال داشته باشه و ۲ هم به ۳
حالا میخواهیم کوتاهترین مسیر رو از ۱ به ۳ چاپ کنیم ، الگوریتم شما ممکنه از ۱ به ۲ بره، بعد برای اینکه چک کنه می شه به ۳ رفت یا نه به طور بازگشتی از ۲ به ۳ بره، حالا یه مسیر جسته، اگه اینو چاپ کنید، که الگوریتم غلطه (چون مستقیم از ۱ به ۳ یال هست )
البته می تونید اینجوری تمام مسیرها را بجورید بعد ببینید کدوم کوتاهتره بعد چاپش کنید، که اصلا بهینه نیست، ولی درسته، یعنی الگوریتم شما برای پیدا کردن یه مسیر از یه راس به راس دیگه درست عمل میکنه، ولی اگه اولین مسیر پیدا شده رو در نظر بگیریم ممکنه کوتاهترین نباشه، در حالی که الگوریتمی وجود داره که اولین مسیری که پیدا می کنه کوتاهترین هم هست و خوب اون بهینه تره، خیلی هم شبیه الگوریتم شماست
 
  • شروع کننده موضوع
  • #8

armita

کاربر خاک‌انجمن‌خورده
ارسال‌ها
2,204
امتیاز
684
نام مرکز سمپاد
دبیرستان فرزانگان ۱
شهر
تهران
دانشگاه
شریف
رشته دانشگاه
‫علوم کامپیوتر‬‎
پاسخ : کوتاه ترین مسیر در گراف

دیگه نظری ندارین ؟ :D
 

zabolian

کاربر نیمه‌حرفه‌ای
ارسال‌ها
235
امتیاز
25
نام مرکز سمپاد
دبیرستان شهید اژه ای اصفهان
شهر
اصفهان
سال فارغ التحصیلی
1390
مدال المپیاد
۳ روز پیش ( ۲۴ اسفند ۸۸) مدال طلای المپیاد کامپیوتر گرفتم
دانشگاه
صنعتی شریف
رشته دانشگاه
مهندسی نرم افزار
پاسخ : کوتاه ترین مسیر در گراف

یه الگوریتم به نام bfs هست که توی گرافهای بدون وزن کوتاهترین مسیر از یه راس به تمام راس‌های دیگه رو حساب میکنه، اونم اینجوریه که دو تا آرایه میگیریم به اندازه تمام راسها یکی واسه‌ی مارک کردن راسهایی که تا حالا رفتیم ( یعنی اگه راس دهم رو یه بار رفتیم مارک خونه دهم رو true میکنیم) اون یکی هم واسه اینکه راسهایی که تاحالا ملاقات کردیم رو به همون ترتیبی که ملاقاتشون میکنیم رو بریزیم تو اون. ( به اینجا که رسید دیدم توضیح فارسی دادن خیلی طول میکشه، کد ++C رو گذاشتم :D )

const int maxn=100*1000;
bool mark[maxn];
int q[maxn];
int dis[maxn];
int par[maxn];


void bfs(int v){
int start=0;
int end=0;
mark[v]=true;
dis[v]=0;
par[v]=-1;
q[end++]=v;
while(start<end){
v=q[start++];
for(int i=0;i<adj[v].size();i++){
if(!mark[adj[v]])
mark[adj[v]=true;
par[adj[v]=v;
q[end++]=adj[v];
dis[adj[v]]=dis[v]+1;
}
}
return;
}


کد بالا کوتاهترین مسیر از راس v به بقیه راس ها رو پیدا میکنه، برای چاپ اندازه مسیر از v به راس i ام از dis و برای چاپ این مسیر با یه تابع بازگشتی از آرایه‌ی par استفاده میکنیم ( پدر هر راس رو تو درخت ریشه دار با ریشه v رو تو خودش نگه میداره)
آرایه adj هم همسایه‌ی های هر راس رو تو خودش نگه میداره

فکر کنم با این توضیحات و با خوندن کد بالا بتونید الگوریتم رو متوجه بشید
 

سروش ربیعی

کاربر نیمه‌فعال
ارسال‌ها
19
امتیاز
3
نام مرکز سمپاد
اورمیه
شهر
اورمیه
دانشگاه
اورمیه
رشته دانشگاه
مهندسی کامپیوتر / نرم‌افزار
پاسخ : کوتاه ترین مسیر در گراف

... و برای گراف‌های وزن‌دار دو فقره الگوریتم هست به اسمای وارشال-کروسکال و دیجکسترا. البته این الگوریتم‌ها درخت‌های فراگیر بهینه رو بیرون میدن. تو این درخت‌ها کوتاه‌ترین فاصله بین دو رأس کمترین وزن مسیر رابط بین اوناست. توضیحات مربوطه رو نمی‌نویسم چون اولاً حال ندارم. دوماً می‌تونین خیلی کامل‌ترشو از ویکی فارسی پیدا کنید:

http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%DA%A9%D8%B1%D9%88%D8%B3%DA%A9%D8%A7%D9%84

http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AF%DB%8C%DA%A9%D8%B3%D8%AA%D8%B1%D8%A7

حواستون باشه که اگه تو گرافتون وزن منفی دارین دایجسترا روش کار نمی‌کنه ها حسن! باید همۀ وزن‌ها رو شیفت بدین تا از منفی بودن دران. و یا اینکه اگه این کار به دلایل معناشناختی ممکن نباشه؛ از الگوریتم بلمن-فورد استفاده کنید.
 

narenjak

کاربر فوق‌حرفه‌ای
ارسال‌ها
863
امتیاز
833
نام مرکز سمپاد
علامه حلی
پاسخ : کوتاه ترین مسیر در گراف

به نقل از سروش ربیعی :
... و برای گراف‌های وزن‌دار دو فقره الگوریتم هست به اسمای وارشال-کروسکال و دیجکسترا. البته این الگوریتم‌ها درخت‌های فراگیر بهینه رو بیرون میدن. تو این درخت‌ها کوتاه‌ترین فاصله بین دو رأس کمترین وزن مسیر رابط بین اوناست. توضیحات مربوطه رو نمی‌نویسم چون اولاً حال ندارم. دوماً می‌تونین خیلی کامل‌ترشو از ویکی فارسی پیدا کنید:

http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%DA%A9%D8%B1%D9%88%D8%B3%DA%A9%D8%A7%D9%84

http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AF%DB%8C%DA%A9%D8%B3%D8%AA%D8%B1%D8%A7

حواستون باشه که اگه تو گرافتون وزن منفی دارین دایجسترا روش کار نمی‌کنه ها حسن! باید همۀ وزن‌ها رو شیفت بدین تا از منفی بودن دران. و یا اینکه اگه این کار به دلایل معناشناختی ممکن نباشه؛ از الگوریتم بلمن-فورد استفاده کنید.

و اضافه کنم روش های داینامیک هم هست ها (البته تا اونجا که یادمه)
 

maziar

مازیمون
ارسال‌ها
1,973
امتیاز
6,845
نام مرکز سمپاد
علامه حلی
شهر
تهران، استانبول، کوالالامپور، اُسلو!
دانشگاه
Universitetet i Oslo
رشته دانشگاه
ریاضی، CS، نانو الکترونیک
پاسخ : کوتاه ترین مسیر در گراف

کلن برایه فکر کردن برایه حل مسائل بهتره اول یه راهه بازگشتی پیدا کنی
چرا که استقرا دقیقن داره بهت اجازه میده با راهه بازگشتی مساله رو حل کنی.
دقیقن ایده ی بی اف اس و دی اف اس همینه
با این فرق که بی اف اس با تفاوتی که با دی اف اس داره کوتاه ترین مسیر رو میده ولی دی اف اس فقط یه مسیر میده جالا کوتاه ترین یا بلند ترین

ولی تو گراف وزن دار باید با دیچیکسترا بری

کد زدنش شاید یه ذره سخت باشه ولی می تونی الگوریتمشو راحت پیده کنی

BFS , DFS
Djkstra

بعد سعی کن خودت کدشو بزنی بی خیاله بیسیک شو.

بعد می تونی راهه حل هایه بهترشو گوگل کنی با اون زبان خاصی که می خوای
 

Dark Eagle

کاربر حرفه‌ای
ارسال‌ها
403
امتیاز
656
نام مرکز سمپاد
helli 2
شهر
Tehran
مدال المپیاد
کامپیوتر
پاسخ : کوتاه ترین مسیر در گراف

به نقل از مازیمون :
کلن برایه فکر کردن برایه حل مسائل بهتره اول یه راهه بازگشتی پیدا کنی
چرا که استقرا دقیقن داره بهت اجازه میده با راهه بازگشتی مساله رو حل کنی.
دقیقن ایده ی بی اف اس و دی اف اس همینه
با این فرق که بی اف اس با تفاوتی که با دی اف اس داره کوتاه ترین مسیر رو میده ولی دی اف اس فقط یه مسیر میده جالا کوتاه ترین یا بلند ترین

ولی تو گراف وزن دار باید با دیچیکسترا بری

کد زدنش شاید یه ذره سخت باشه ولی می تونی الگوریتمشو راحت پیده کنی

BFS , DFS
Djkstra

بعد سعی کن خودت کدشو بزنی بی خیاله بیسیک شو.

بعد می تونی راهه حل هایه بهترشو گوگل کنی با اون زبان خاصی که می خوای
اگه هدفتون پیدا کردن کوتاه ترین مسیر بین هر دو راس باشه با n تا BFS میشه به جواب رسید که اوردرش n به توانه 3 اه......... :-"
از یه روش دیگه هم میشه استفاده کرد که تقریبا شبیه پویا میمونه ............. :-"
اونم اوردرش n به توان 3 اه ولی کلا با BFS فرق داره ............ :-"
الان اسمش یادم نیس ولی تو مایه های پویاست............ ;;)
BFS / DFS رو زیاد گنده نکنید .......... B-)
چیزه خیلی خاصی نداره فقط یادتون باشه قبل مرحله 3 چند بار کدشو بزنید دستتون راه بیفته........... ;;)
داش مازیمون دایسترا اه نه دیجکسترا ..........(فارسیشو میگم) 8->
یک سوال : میشه BFS / DFS رو با هم قاطی کرد یعنی تو بعضی حالت ها با چک کردن یه if یکیشون رو بزنه تو else اش اون یکی رو..........
؟؟؟
B-)
 

kerpoocoder

کاربر نیمه‌حرفه‌ای
ارسال‌ها
240
امتیاز
1,057
نام مرکز سمپاد
علامه حلی غیر چینی
شهر
کرمون
مدال المپیاد
یه کم
دانشگاه
شهید باهنر کرمان
رشته دانشگاه
CS &amp; Math
پاسخ : کوتاه ترین مسیر در گراف

پستا رو که می خوندم به نظرم از سال 2009 تا الان خیلی مطلب جامعی در مورد این مسئله ارائه نشده من سعی می کنم ی توضیح کاملی ارائه بدم باشد که مفید واقع گردد.

کلا چهار تا الگوریتم معروف برای حل این مسئله وجود داره که هر کدوم جایی کاربرد دارن و نقاط ضعف و قوتی نسبت به بقیه دارن

هر کدوم از اینا رو تو ویکی سرچ کنید همه چی رو درباره شون میاره من فقد نقاط ضعف و قوتشون و رو می گم

1- Floyed-Warshall

یه الگوریتمه داینامیک از (O(n^3 هست[nb]منظور از n و |V| همون تعداد راس و |E| همون تعداد یال هست .[/nb] که پیاده سازی راحتی داره کوتاهترین فاصله بین هر دو راس از گراف رو بعد از اجرا توی ی ماتریس دارین برای تمام گراف ها هم درست کار می کنه (یال های وزن دار حتی منفی به شرطی که دور منفی نداشته باشیم) ایراد این الگوریتم اولا زمان اجراشه ثانیا کوتاهترین مسیر رو تو گراف بین دوتاراس نمی تونید چاپ کنید فقط میتونید طولشو داشته باشید. :D

2- dijkstra

یه الگوریتم گریدی که برای گراف های با یال وزن دار (وزن های غیر منفی) کوتاهترین مسیر رو ارائه می ده زمانش هم (|O(|E|log|v هست البته با ساختمان داده fibonacci heap می شه با زمان (|O(|v|^2+|v|log|v پیاده ش کرد که زمانش بسته به گراف بین vlogv و v^2 متغیره.
فقط کوتاهترین فاصله بین یک راس و سایر راس ها رو بهتون می ده و خوبی دیگه ای هم داره اینه که می تونید ی درخت dijkstra موقع اجرا درست کنید که بعد از اجرا یکی از کوتاهترین مسیر های بین دو راس رو با یه DFS یا BFS تو درخته چاپ یا ذخیره کنید. اما برای گراف هایی با یال منفی درست کار نمی کنه.

3- Bellman-ford

این الگوریتم برای گراف های با دور منفی هم کوتاهترین مسیر رو چاپ می کنه زمانش هم (|O(|E|*|V و می تونه تشخیص بده بین دو راس یک کوتاهترین مسیر وجود داره یا یک دور منفی وجود دارد (دور منفی باعث ایجاد یک لوپ میشود که کوتاهترین فاصله را در هر مرحله کم تر می کند)

4- BFS

این الگوریتم از (|O(|E هست (E تعداد یال های اون مولفه همبندی مونه البته توی این مسئله خاص زمانش کم شده توی کابرد های دیگه تعداد راس ها و کل یال ها هم مهم می شه) که فقد برای گراف های بی وزن درست کار می کنه در واقع توی این مسئله حالت خاص الگوریتم دایکسترا برای گراف های بی وزنه که عمل سرچ کردن ازش حذف شده و اون logv که به صورت ضرب اومده بود برداشته می شه. چون همه یال های هم وزنن دیگه نیازی به سرچ نیست و سطح به سطح یال ها رو طی می کنیم. :)
پس بچه اون محسوب می شه و برای گراف های بی وزن همون خواص دایکسترا رو داره. :) مثه چاپ مسیر و درخت BFS :D

خب فک کنم برای کسایی که می خوان برن رو شاخ این مسئله الان بدونن باید چه کار کنن :D
 

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
570
امتیاز
2,993
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : کوتاه ترین مسیر در گراف

به نقل از به یاد نصیر :
2- dijkstra

یه الگوریتم گریدی که برای گراف های با یال وزن دار (وزن های غیر منفی) کوتاهترین مسیر رو ارائه می ده زمانش هم (|O(|E|log|v هست البته با ساختمان داده fibonacci heap می شه با زمان (|O(|v|^2+|v|log|v پیاده ش کرد که زمانش بسته به گراف بین vlogv و v^2 متغیره.
فقط کوتاهترین فاصله بین یک راس و سایر راس ها رو بهتون می ده و خوبی دیگه ای هم داره اینه که می تونید ی درخت dijkstra موقع اجرا درست کنید که بعد از اجرا یکی از کوتاهترین مسیر های بین دو راس رو با یه DFS یا BFS تو درخته چاپ یا ذخیره کنید. اما برای گراف هایی با یال منفی درست کار نمی کنه.
همش قبول ولی دایسترا گریدیه؟
 

kerpoocoder

کاربر نیمه‌حرفه‌ای
ارسال‌ها
240
امتیاز
1,057
نام مرکز سمپاد
علامه حلی غیر چینی
شهر
کرمون
مدال المپیاد
یه کم
دانشگاه
شهید باهنر کرمان
رشته دانشگاه
CS &amp; Math
پاسخ : کوتاه ترین مسیر در گراف

آره دیگه شبیه پریم هم هست.
تو هر مرحله از بین مجموعه راس هایی که به راس های درختمون تا الان وصلن اونی رو به درخت اضافه میکنیم که مجموع یال بین خودش و پدرش+فاصله پدر از ریشه از بقیه راس ها کمتر باشه بچه هاش رو هم اضافه که می کنیم با یال پدر فعلی شون+فاصله پدر تا ریشه در صورت وجود مقایسه می کنیم کمترین رو پدر اون راس قرار میدیم کاملا نگرش گریدی داره. :D خود مسئله هم که دنبال ی کمینه ست.
 

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
570
امتیاز
2,993
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : کوتاه ترین مسیر در گراف

ولی من هنوزم فکر میکنم دی پیه :D
ولی قبول دارم که نگرش گریدی هم داره :-"
مثل اون سواله پیدا کردن زیردنباله ی متوالی با بیشینه مجموع عناصر هست که هم میشه به دید گریدی نگاهش کرد و هم میشه به دید دی پی نگاهش کرد :/

پ.ن: #نبش_قبر
 

hamid.iran

کاربر جدید
ارسال‌ها
2
امتیاز
1
نام مرکز سمپاد
علامه حلی
شهر
تهران
سال فارغ التحصیلی
1388
دانشگاه
سازمان نقشه برداری و علوم جغرافیایی
سلام به همه عزیزان
دوستان بزرگوار برای حل این مسئله نیاز به کمک دارم.بی نهایت سپاسگزارم

✅سوال:
یک آرایه دو بعدی با ۴ ستون و n سطر مفروض است.
۱- ستون اول نام نود (مثلاً A)
۲- ستون دوم نام نود بعدی (مثلا B)
۳- ستون سوم هزینه ناخالص رفتن از نقطه A به نقطه B
۴- ستون چهارم خالص هزینه رفتن از نقطه A به نقطه B
۵- هزینه رفتن از A به B یا از B به A یکی است
A -> B = B -> A

۶- حداقل باید بیش از ۲ نود پیمایش شود مثلا
A -> B -> C -> A
--------------------------------------
خواسته الگوریتم:

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

نکته: گاهی اوقات ممکن است خالص هزینه محاسبه شده در یک مرحله منفی هم باشد.
-------------------------------------
بطور مثال ماتریس زیر :
A - B - 0.6 - (0.03)
B - C - 8.18 - (-1.05)
A - C - 4.16 - (2.01)
C - D - 7.22 - (-0.52)
B - D - 12.01 - (0.71)
A - D - 3.45 - (1.35)
 
بالا