מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Dijkstra/תרגילים/Dijkstra עם המסלולים הזולים ביותר/שאלה

בהרצאה ראינו את אלגוריתם Dijkstra בגרסה המחזירה רק את מחירי המסלולים הזולים ביותר. נזכר בממשק ובשימוש בו. נניח שהגרף הוא המתואר בתרשים הבא:

בעיית המסלול הזול ביותר.

אז קטע הקוד הבא מדגים שימוש אפשרי:

1		Min-Costs = Dijkstra(G, Edge-Costs, 1)

	# Prints 0.
2	Print( Min-Costs[1] )

	# Prints 6.
3	Print( Min-Costs[3] )

כעת רוצים לשנות את האלגוריתם Dijkstra כך שיחזיר זוג מערכים: הראשון ממפה כל צומת לעלותו המינימלית מs (כמו שעושה המערך היחיד המוחזר עד כה), והשני ממפה כל צומת למסלול עלות מינמלי מs אליו.

אם הגרף הוא הגרף שראינו לעיל, אז קטע הקוד הבא מדגים שימוש אפשרי בגרסה החדשה:

Print-Path(Path)
1	for i in [1, ..., Length(Path)]
2		Print Path[i]



1	(Min-Costs, Min-Paths) = Dijkstra(G, 1)

	# Prints 0
2	Print( Min-Costs[1] )

	# Prints nothing
3	Print-Path( Min-Paths[1] )

	# Prints 6
4	Print( Min-Costs[3] )

	# Prints (1, 6), (6, 7), (7, 3)
5	Print-Path( Min-Paths[3] )
		
	# Prints 9
6	Print( Min-Costs[4] )

	# Prints (1, 6), (6, 7), (7, 3), (3, 4)
7	Print-Path( Min-Paths[4] )

אנא כתוב את השינויים המתאימים ונתח את הסיבוכיות.