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

ÇÑŵ¿   
   Á¶È¸ 5327   Ãßõ 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 3152/5687
2014-05   4990871   Á¤ÀºÁØ1
2015-12   1526861   ¹é¸Þ°¡
2005-12   5329   ¹Ú¿ì¿­
2007-09   5329   ¼­¼öºÀ
2006-01   5329   Àü°æ¿õ
2006-03   5329   ±è¹Îö
2019-02   5329   ÀÌõdz
2016-11   5329   ÄĹÚ
2020-02   5330   ghostman
2014-08   5330   µ¥·Ô
2014-10   5330   ÇʵåÅ×½ºÅÍ
2008-03   5330   ¿ì½Â¿±
2006-03   5330   ¹ÚÁؼö
2005-12   5330   ¹æÈ¿¹®
2006-03   5330   ½É±Ô»ó
2017-01   5330   ±èÀº¸ñ
2007-06   5330   ¿À¼º±â
2007-02   5330   Çã´ë¿õ
2008-04   5330   ±èÁö¿î
2005-10   5330   ÀÌ»ó·æ
2009-01   5330   ±è°æ·Ï
2015-03   5330   ÀüÁ÷P¿¬±¸¿ø