המסלול הקצר ביותר
שיעור 12 מתוך 14 בקורס גרפים – סדרת מבני נתונים מס' 9 של Coddy.
כמה מעט קשתות צריך כדי להגיע מ־start ל־end? בגרף לא משוקלל (לכל הקשתות אותה עלות), התשובה היא בדיוק מה ש־BFS מחשב. מכיוון ש־BFS מבקר בקודקודים לפי מרחק עולה מנקודת ההתחלה, בפעם הראשונה שנגיע אל end נעשה זאת לאורך המסלול הקצר ביותר.
הטריק הוא להכניס לתור כל קודקוד יחד עם המרחק אליו עד כה. מתחילים עם (start, 0). בכל פעם שמגלים שכן חדש v מקודקוד במרחק d, מכניסים לתור את (v, d + 1). כאשר v == end, מחזירים את d + 1.
שני מקרי קצה. אם start == end, התשובה היא 0. אם BFS מסתיים בלי להגיע אי פעם אל end, השניים נמצאים ברכיבי קשירות שונים, והתשובה היא -1.
אתגר
קלכתבו פונקציה shortestPath שמקבלת מערך int דו־ממדי adjacency, ערך int בשם start וערך int בשם end, ומחזירה את המרחק הקצר ביותר (מספר הקשתות) מ־start ל־end.
- אם
start == end, החזירו0. - אם אי אפשר להגיע אל
endמ־start, החזירו-1. - אחרת, החזירו את מספר הקשתות המינימלי ביניהם.
עליכם להשתמש במחלקה Graph (המסופקת בקובץ graph) — אל תשתמשו במבנים המובנים בשפה (מפות, קבוצות) כדי לייצג את רשימת השכנויות. נתוני עזר עבור האלגוריתם (קבוצות ביקור, תורים) יכולים להשתמש בטיפוסים מספריית התקן.
נסו בעצמכם
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start, end;
if (scanf("%d %d %d %d", &n, &m, &start, &end) != 4) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", shortestPath(adjacency, m, start, end));
return 0;
}
כל השיעורים ביחידה גרפים – סדרת מבני נתונים מס' 9
תרגלו בעצמכם: קומפיילר C אונליין