PDA

View Full Version : الگوریتم کوتاهترین مسیر بین دو نود وقتی که وزن همه یال ها یکسان باشه؟



root88
جمعه 10 دی 1389, 21:16 عصر
سلام اگه بخواهم کوتاهترین مسیر بین دو نود از یه گراف رو به دست بیاریم به شرطی که وزن همه یالها یکی باشه از چه الگوریتمی استفاده کنم؟ مرتبه زمانیش باید حداکثر O(E log V) باشه. من دیکسترا با هیپ رو دارم اما نمی دونم کجاهاش باید تغییر بدم که وقتی وزن یالها یکی هست هم کوتاهترین مسیر رو بده و خود مسیر رو.