گراف بدون جهت و وزندار G و رأس مشخص s از این گراف را درنظر بگیرید. از الگوریتم دایکسترا برای محاسبه کوتاهترین مسیر ساده از s به بقیه رئوس استفاده کردهایم. بهازای چند حالت زیر این الگوریتم با وجود وزنهای منفی همیشه درست کار میکند؟ هر یالی بتواند وزن منفی داشته باشد. تنها یالهای منتهی به s بتوانند وزن منفی داشته باشند. تنها یالهای برشی گراف G بتوانند وزن منفی داشته باشند. بهازای هر دور گراف G حداکثر یک یال بتواند وزن منفی داشته باشد.

سوال ۶۹ کنکور ارشد مهندسی کامپیوتر ۱۴۰۰

طراحی الگوریتم‌هاسختالگوریتم‌های حریصانه

اهمیت

۰/۵

گراف بدون جهت و وزن‌دار $G$ و رأس مشخص $s$ از این گراف را درنظر بگیرید. از الگوریتم دایکسترا برای محاسبه کوتاه‌ترین مسیر ساده از $s$ به بقیه رئوس استفاده کرده‌ایم. به‌ازای چند حالت زیر این الگوریتم با وجود وزن‌های منفی همیشه درست کار می‌کند؟

هر یالی بتواند وزن منفی داشته باشد.
تنها یال‌های منتهی به $s$ بتوانند وزن منفی داشته باشند.
تنها یال‌های برشی گراف $G$ بتوانند وزن منفی داشته باشند.
به‌ازای هر دور گراف $G$ حداکثر یک یال بتواند وزن منفی داشته باشد.

#dijkstra#shortest-path#negative-weights#bridge-edges#negative-cycle#undirected-graph