cpdebugger
New member
מציאת השביל הקצר ביותר בגרף
הבעייה: נתון גרף עם משקלים V – vertices E-Edges כל צמת מחוברת בקשת ל-1 – V צמתים (בהכרח קיים מסלול בין כל צמת לצמת). שלב א: אני מעוניין למצוא לכל צמת את הצמת הכי רחוקה ממנה בגרף. כלומר לכל צמת v למצוא את כל המרחקים הקצרים ביותר בינה ובין שאר הצמתים בגרף, ומבין כל המרחקים הללו לברור את הארוך ביותר. שלב ב: למיין לפי אורך את המרחקים הקצרים הארוכים שמצאתי בשלב א. חשבתי על אלגו floyd – Warshall למציאת מסלול קצר בין כל ה vertices כי הוא רץ בסיבוכיות של V בשלישית. שאלה 1: אולי מישהו יכול לחשוב על אלגו אחר, כי למעשה אני לא זקוק לכל המרחקים הכי קצרים בין כל זוג צמתים (יש כאלו V בריבוע), רק לכל צומת את המסלול הארוך ביותר ממנה לצמת אחרת (יש כאלו V). שלב ג': תוך כדי ריצה של האפליקציה נמחקים צמתים בגרף אבל עדיין מתקיים התנאי שבהכרח קיים מסלול בין כל צמת לצמת אחרת. אני צריך למצוא שוב לכל צמת את הצמת הכי רחוקה ממנה בגרף ולמיין את המרחקים. האפשרות הפשוטה היא להריץ את האלגוריתם של שלבים א' ו ב' מחדש. שאלה 2: האם יש דרך לייעל את ג'. להחזיק מבני נתונים שיאפשרו פתרון מבלי לחשב מחדש את כל המרחקים בגרף?
הבעייה: נתון גרף עם משקלים V – vertices E-Edges כל צמת מחוברת בקשת ל-1 – V צמתים (בהכרח קיים מסלול בין כל צמת לצמת). שלב א: אני מעוניין למצוא לכל צמת את הצמת הכי רחוקה ממנה בגרף. כלומר לכל צמת v למצוא את כל המרחקים הקצרים ביותר בינה ובין שאר הצמתים בגרף, ומבין כל המרחקים הללו לברור את הארוך ביותר. שלב ב: למיין לפי אורך את המרחקים הקצרים הארוכים שמצאתי בשלב א. חשבתי על אלגו floyd – Warshall למציאת מסלול קצר בין כל ה vertices כי הוא רץ בסיבוכיות של V בשלישית. שאלה 1: אולי מישהו יכול לחשוב על אלגו אחר, כי למעשה אני לא זקוק לכל המרחקים הכי קצרים בין כל זוג צמתים (יש כאלו V בריבוע), רק לכל צומת את המסלול הארוך ביותר ממנה לצמת אחרת (יש כאלו V). שלב ג': תוך כדי ריצה של האפליקציה נמחקים צמתים בגרף אבל עדיין מתקיים התנאי שבהכרח קיים מסלול בין כל צמת לצמת אחרת. אני צריך למצוא שוב לכל צמת את הצמת הכי רחוקה ממנה בגרף ולמיין את המרחקים. האפשרות הפשוטה היא להריץ את האלגוריתם של שלבים א' ו ב' מחדש. שאלה 2: האם יש דרך לייעל את ג'. להחזיק מבני נתונים שיאפשרו פתרון מבלי לחשב מחדש את כל המרחקים בגרף?
