1, 2 - הי, בשאלה נתון גרף מכוון, שני צמתים אס וטי, ושתי פונקציות משקל.
אין בגרף מעגלים שליליים באךף אחת מפונקציות המשקל. מבקשים למצוא מבין המסלולים הקלים מאס לטי לפי פ׳ משקל 1 את אלו הקלים לפי פ׳ משקל 2.
האם ניתן לעשות זאת על ידי הרצת דייקסטרה אחת, בה כל החלטה מתבצעת על ידי זוג המשקלים (בסדר לקסיקוגרפי)?
ואז להוכיח את נכונות האלגוריתם ״החדש״?
או שהפתרון יכול להיות רק על ידי הרצת בלמן פורד פעמיים?
תודה רבה.