אם נתון גרף, שהמשקלות בו שליליים וחסומים:
w:E->{-1,-2,…,-10}
ונתון צומת התחלה, שרוצים למצוא ממנו מק"בים לשאר הצמתים בגרף,
אפשר להפוך את הסימן של כל המשקלות, ואז להריץ דייקסטרה רק כשהפעם מחפשים מסלול כבד ביותר?
בפונק' האתחול נותנים ערך מינוס אינסוף לצומת ההתחלה וערך 0 לשאר הצמתים,
(d[s]= -inf, d[v]=0 for all v in V\{s})
והרילקס ישתנה ל:
if d[v]<d[u]+w(u,v)
אם התשובה היא כן האם אפשר להשתמש בטריק שראינו בדייקסטרה כאשר המשקלות חסומים ולהשיג זמן ריצה טב יותר?
תודה.