سوال ۷۳ کنکور ارشد علوم کامپیوتر ۱۴۰۴

یک گراف جهت‌دار $G=(V,E)$ مدلی برای یک شبکه کامپیوتری با $n$ رأس است. وزن $w(u,v)$ روی یال $(u,v)$، احتمال خراب‌نبودن (سالم‌بودن) لینک $(u,v)$ است. فرض کنید لینک‌ها مستقل از یکدیگر خراب می‌شوند، بنابراین احتمال خراب‌نبودن یک مسیر برابر حاصل‌ضرب وزن $w$ یال‌های آن است. می‌خواهیم برای هر دو رأس، مقدار $P_{ij}$ یعنی بیشترین احتمال خراب‌نبودن مسیر بین دو رأس $i$ و $j$ (مطمئن‌ترین مسیر) را به‌دست آوریم. از الگوریتم زیر استفاده می‌کنیم که در آن $P_{ij}^{(k)}$ بهترین مقدار روی مسیرهایی است که همهٔ رأس‌های میانی آن‌ها از مجموعهٔ $\{1,2,\dots,k\}$ باشند:

for(k = 1 ; k <= n ; k++)
  for(i = 1 ; i <= n ; i++)
    for(j = 1 ; j <= n ; j++)
      (a)

کدام عبارت سطر $(a)$ را به‌درستی پر می‌کند تا الگوریتم درست باشد؟