¾Ë°í¸®ÁòÀ» ÀÚ¹Ù·Î Ç®´Ù°¡ ¸·Çû½À´Ï´Ù.

ÇÑŵ¿   
   Á¶È¸ 5865   Ãßõ 8    

shortestPath(v, weight, n)

     // v´Â ½ÃÀÛÁ¡, weight´Â °¡ÁßÄ¡ ÀÎÁ¢ Çà·Ä, nÀº Á¤Á¡¼ö

     // create S[n], Dist[n]

   for (i¬0; i<n; i¬i+1) do {

         S[i] ¬ false;  // S¸¦ ÃʱâÈ­

         Dist[i] ¬ weight[v, i];  // Dist¸¦ ÃʱâÈ­

   }

   S[v] ¬ true;

   Dist[v] ¬ 0;

   for (i¬0; i<n-2; i¬i+1) do {  // n-2¹ø ¹Ýº¹

         select u such that  // »õ·Î¿î ÃÖ´Ü °æ·Î¸¦ ¼±Á¤

               Dist[u] = min{Dist[j] | S[j] = false and 0¡Âj<n};  

         S[u] ¬ true;

         for (w¬0; w<n; w¬w+1) do {  // È®Á¤ÀÌ ¾ÈµÈ °æ·Îµé¿¡ ´ëÇØ ´Ù½Ã °è»ê

               if (S[w] = false) then {

                     if (Dist[w] > (Dist[u] + weight[u, w])

                           then Dist[w] ¬ Dist[u] + weight[u, w];

   }}}

end shortestPath




==================================================================================

À§¿¡°É º¸°í ÀÚ¹Ù·Î º¯È¯À» Çϴµ¥

select u such that Àú ºÎºÐÀ» ¾î¶»°Ô º¯È¯ÇؾߵÉÁö ¸ð¸£°Ú½À´Ï´Ù.

¿äºÎºÐ¸¸ ÇØ°áÇÏ¸é µÉµíÇѵ¥ ÀÚ¹Ù¸¦ ´Ù ¾È¹è¿ì°í ¾Ë°í¸®ÁòÀ» ÇÏ´ÂÁö¶ó... Àß ¸ð¸£°Ú½À´Ï´Ù.

¾Ë·ÁÁÖ½Ã¸é °¨»çÇϰڽÀ´Ï´Ù.
ªÀº±Û Àϼö·Ï ½ÅÁßÇϰÔ.


QnA
Á¦¸ñPage 4274/5752
2015-12   1891076   ¹é¸Þ°¡
2014-05   5376880   Á¤ÀºÁØ1
2008-11   5366   ÀÌÀÎ
2008-11   5634   ±è»óÀÏ
2008-11   5757   ±èÁ¾¼º
2008-11   6097   ¹èÁ¤ÇÑ
2008-11   5865   ±èÇö¿ì
2008-11   6217   ¹ÎºÀ±â
2008-11   5591   ±èÈ¿¼ö
2008-11   5805   Çѵ¿ÈÆ
2008-11   6178   ¹Ú¿µ¼±
2008-11   8701   ±èÈ£¼º
2008-11   5635   Á¶¿µ¼ö
2008-11   5305   ¹Úµ¿¼±
2008-11   5423   ¹æÈ¿¹®
2008-11   5680   ¿ì½Â¿±
2008-11   5981   ±è½Â±Ç
2008-11   5476   À庴µÎ
2008-11   6643   Çѵ¿ÈÆ
2008-11   5659   ±è°Ç¿ì
2008-11   5112   ±èÀç½Ä
2008-11   5947   Á¤Çüö