שאלה באלגוריתמים
בגרף לא ממושקל G "מסלול קצר ביותר" בין v ל-u, הוא מסלול בין v ל-u בעלת מספר הקשתות המינימלי מבין כלל המסלולים מ-u ל-v.
אני צריך לכתוב אלגוריתם יעיל, כך שבהינתן גרף מכוון G, קדקד מקור v, וקדקד יעד u, מחזיר את כמות המסלולים הקצרים ביותר מ-v ל-u.
(מסלול יכלל בקבוצת המסלולים הקצרים ביותר הנמנית, אם הוא שונה בלפחות קדקד אחד מיתר המסלולים בקבוצה).
השאלה הזו היא מתוך תרגיל שרלוונטי לאלגוריתם BFS, לכן הפתרון צריך להתבסס עליו
יתכן שאפשר לפתור את זה גם בדרכים אחרות או ע"י אלגוריתמים שאני לא מכיר..אבל זו לא הכוונה.
ממה שאני יודע, BFS שמופעל על קדקד מקור s, נותן לי את אורך המסלול הקצר ביותר מ-s לכל קדקד (עבור כל קדקד, יש שדה
שיכיל את אורך המסלול הקצר ביותר ממנו לקדקד המקור s.).
לכן בשאלה כאן, אם אפעיל את BFS עם קדקד המקור v, אז ברגע ש-u יהפוך מלבן לאפור, הוא יתעדכן עם המרחק הקצר ביותר ממנו ל-v.
השאלה איך אני כמה מסלולים יש מ-v ל-u, וכמה מתוכם הם באורך מינימלי.
מניח שצריך לעשות פה איזשהו שינוי באלגוריתם, אבל אני לא מצליח לעלות על השינוי הזה.
מישהו יכול בקשה לעזור?
תודה.
בגרף לא ממושקל G "מסלול קצר ביותר" בין v ל-u, הוא מסלול בין v ל-u בעלת מספר הקשתות המינימלי מבין כלל המסלולים מ-u ל-v.
אני צריך לכתוב אלגוריתם יעיל, כך שבהינתן גרף מכוון G, קדקד מקור v, וקדקד יעד u, מחזיר את כמות המסלולים הקצרים ביותר מ-v ל-u.
(מסלול יכלל בקבוצת המסלולים הקצרים ביותר הנמנית, אם הוא שונה בלפחות קדקד אחד מיתר המסלולים בקבוצה).
השאלה הזו היא מתוך תרגיל שרלוונטי לאלגוריתם BFS, לכן הפתרון צריך להתבסס עליו
יתכן שאפשר לפתור את זה גם בדרכים אחרות או ע"י אלגוריתמים שאני לא מכיר..אבל זו לא הכוונה.
ממה שאני יודע, BFS שמופעל על קדקד מקור s, נותן לי את אורך המסלול הקצר ביותר מ-s לכל קדקד (עבור כל קדקד, יש שדה
שיכיל את אורך המסלול הקצר ביותר ממנו לקדקד המקור s.).
לכן בשאלה כאן, אם אפעיל את BFS עם קדקד המקור v, אז ברגע ש-u יהפוך מלבן לאפור, הוא יתעדכן עם המרחק הקצר ביותר ממנו ל-v.
השאלה איך אני כמה מסלולים יש מ-v ל-u, וכמה מתוכם הם באורך מינימלי.
מניח שצריך לעשות פה איזשהו שינוי באלגוריתם, אבל אני לא מצליח לעלות על השינוי הזה.
מישהו יכול בקשה לעזור?
תודה.
