الگوریتم فلوید

از ویکی جامع پردیس دانشگاهی دانشگاه قم
پرش به: ناوبری، جستجو
الگوریتم یافتن کوتاه ترین مسیر:
viod floyd(int n, const number W[] [], number D [] [], index P[] [])
{
   index i, j, k
   for(i=1; i<= n; i++)
      for(j=1; j<= n; j++)
         P[i] [j] = 0
   D= W
      for(k= 1; k<= n; k++)
         for(i= 1; i<= n; i++)
            for(j= 1; j<= n; j++)
               if(D[i] [k] + D[k] [j] < D[i] [j])
               {
                  P[i] [j] = k
                  D[i] [j] = D[i] [k] + D[k] [j]
               }
}

الگوریتم چاپ کوتاه ترین مسیر:
void path(index q, r)
{
   if(P[q] [r] != 0)
   cout<<" v " << P[q] [r]
   path(P[q] [r] , r)
}