backtracking

יוגי משוטט ברחבי מדינה בת N ערים. הוא נעזר במטריצת כבישים NXN ,בה התא ה- (j,i (מכיל את
אורך הכביש המחבר בין העיר i לעיר j .זוהי מטריצה בה איברי האלכסון הראשי שווים 0 ,שאר
האיברים חיוביים ממש, והיא אינה בהכרח סימטרית (ייתכנו כבישים חד- סטריים).
יוגי שם לב שהכביש הישיר בין שתי ערים אינו בהכרח הדרך הקצרה ביותר לעבור ביניהן, כלומר
לעתים משתלם לעבור דרך ערים אחרות.
כתבו תוכנית הקולטת מטריצה NXN עבור 4=N) יש להגדיר זאת ב- define ,(עיר מקור ועיר יעד
(מובטח כי הן שונות), ומדפיסה עבור יוגי את המסלול הקצר ביותר מהמקור ליעד (כולל המקור
והיעד).
הערות:
1 .יש לפתור באמצעות backtracking ולהימנע מחישובים מיותרים.
2 .מובטח כי קיים מסלול קצר ביותר יחיד בין המקור ליעד.
3 .ניתן להניח שהקלט תקין, ואין צורך לבדוק זאת.