این مسئله یک راه سریع و کثیف برای ساختن یک نقشه شبکه از روی یک نقشه واقعی را نشان می دهد. بخش (الف) را می توان به راحتی انجام داد و بیشتر بینش را منتقل می کند. بخش‌های باقی‌مانده زمان‌بر اما مهم هستند تا رویکردی داشته باشیم که به طور کلی خوب کار کند.
یک نقشه فرضی را در نظر بگیرید که شهرهای 1 تا 4 دارای مختصات به ترتیب (0،0)، (4،0) (4،3)، و (3.0)، هستند.. مختصات بر حسب اینچ مشخص شده است و مقیاس نقشه 60 مایل بر اینچ است. قوس‌های (1،2)، (1،3)، (2.3)، (4;2)، و (4، (3 بخش‌های جاده‌ای را در جفت شهرها نشان می‌دهند، و هر طول به عنوان حاصلضرب مقیاس نقشه تقریبی می‌شود. و فاصله اقلیدسی بین مختصات مرتبط (مثلاً طول قوس (1.2) به صورت تقری240 مایل است) بنابراین طول ها به ترتیب فهرست شده اند. قوس‌ها 240، 300، 180، 240 و 300 هستند. (الف) برنامه‌ای بنویسید که تمام این داده‌ها را از یک فایل ورودی مرتب شده در داخل بخواند و طول قوس را محاسبه کند. توجه داشته باشید که مقیاس نقشه ابتدا و تعداد رئوس در مرحله دوم ذکر شده است. سپس مختصات رئوس را دنبال کنید و اطلاعات مربوط به کمان ها را دنبال کنید (e… رئوس 2 و 3 در مجاورت رئوس 1. 3. و 4 مجاور راس 2 هستند. و به همین ترتیب -I برای نشان دادن پایان خط است).
تقریب طول ها با فواصل اقلیدسی، فاصله های واقعی را دست کم می گیرد، و افزایش عاقلانه مقیاس نقشه می تواند این کم برآورد را کاهش دهد.
اطلاعات قوس به طور عمدی تکرار می شود تا احتمال حذف یک قوس به اشتباه کاهش یابد. یک رویکرد دقیق تر برای طول قوس، البته، استفاده از فواصل واقعی است، اما این نیاز به تلاش بسیار بیشتری برای به دست آوردن و وارد کردن داده ها دارد، که در نتیجه رویکردی نه سریع و نه کثیف است. طول ها را در یک ماتریس به صورت زیر چاپ کنید (“inf” نشان دهنده بی نهایت است، یعنی هیچ قوسی وجود ندارد):
(ب) برنامه خود را تعمیم دهید تا تعداد دلخواه رئوس m را مدیریت کند، در حالی که از همان قالب ورودی اولیه و رویکرد محاسباتی استفاده کنید.
ج) توجه داشته باشید که ماتریس قسمت (الف) به شکل مورد نیاز برای الگوریتم فلوید است. برای محاسبه کوتاه‌ترین فاصله بین هر جفت رئوس، کدی برای الگوریتم فلوید به برنامه قسمت (ب) خود اضافه کنید. ماتریس فاصله را در حافظه ذخیره کنید و آن را در یک فایل خروجی بنویسید. هر فاصله محاسبه شده را به نزدیکترین عدد صحیح گرد کنید.
(د) یک مسیر فرعی بنویسید تا به صورت گرافیکی – روی یک مانیتور ویدئویی – مکان های رأس و ناحیه های متصل به آنها نمایش داده شود. هر مکان راس را با یک مربع یا دایره، و کمان ها را با پاره های خطی که به مکان های راس مرتبط می پیوندند، نشان دهید. اگر مانیتور رنگی دارید، رئوس را با رنگ سبز و کمان ها را به رنگ زرد نشان دهید.
(ه) کد قسمت (e) خود را تعمیم دهید تا مسائل 1مرکز وزنی محدود شده و مسائل 1 میانه وزن نشده را حل کنید. راه حل های یافت شده با رنگ قرمز را روی یک مانیتور رنگی نشان دهید (با فرض اینکه قسمت (د) را انجام داده اید).
(کد قسمت (c) خود را تعمیم دهید تا در یک نام برای هر رأس خوانده شود (مثلاً نام شهر یا هویت یک تقاطع). رویه ای بنویسید که برای هر عدد رأس درخواستی، نام را در راس بنویسد. صفحه نمایش و به یک فایل خروجی.