=>¼³¸í
¨è¹øÀÇ ÃִܰŸ®ÀÇ 1Çà( 0 1 3 1 4 5)¿Í ¨ê¹øÀÇ °¢ Á¤Á¡¿¡ ´ëÇÑ (ÃִܰŸ®: x)¸¦ ºñ±³Çغ¸¸é °°À½À» ¾Ë¼ö ÀÖ´Ù.(ÇÁ·Î±×·¥ÀÌ Á¦´ë·Î ±¸ÇöµÇ¾úÀ½À» ÀǹÌ)
Dijkstra ¾Ë°í¸®Áò¿¡¼ Å×½ºÆ®1ÀÇ ±×·¡ÇÁ(grape.dat)¸¦ µ¿ÀÏÇÑ °ÍÀ¸·Î Çß´Ù. Floyd ¾Ë°í¸®Áò°ú °á°ú¸¦ ºñ±³Çϱâ À§ÇؼÀÌ´Ù. ¨ê¹øÀÇ °á°ú¸¦ À¯½ÉÈ÷ ºÁµÎ¸é ÁÁ°Ú´Ù.
¢ºÅ×½ºÆ®2 (ÆÄÀϸí: floyd2.dat)
¢º½ÇÇà°á°ú2
=>¼³¸í
¨è¹øÀÇ ÃִܰŸ®ÀÇ 1Çà( 0 2 6 3 6 3 5 9 )¿Í ¨ê¹øÀÇ °¢ Á¤Á¡¿¡ ´ëÇÑ (ÃִܰŸ®: x)¸¦ ºñ±³Çغ¸¸é °°ÀºÀ» ¾Ë¼ö ÀÖ´Ù.(ÇÁ·Î±×·¥ÀÌ Á¦´ë·Î ±¸ÇöµÇ¾úÀ½À» ÀǹÌ)
2. Greedy - Dijkstra ¾Ë°í¸®Áò
¢ºdijkstra ¾Ë°í¸®Áò ¼Ò½º(ÆÄÀϸí: dijkstra.cpp)
#include
#include
#include //ÆÄÀÏ¿¡ ÀÔÃâ·ÂÀ» À§Çؼ
using std::ofstream;
using std::ifstream;
//ÀÌÀ½¼± ±¸Á¶Ã¼ Á¤ÀÇ
struct edge {
int start_v;
int end_v;
};
const int MAX=11;//vertexÃÖ´ë 10°³ test(1~10¹ø index»ç¿ë)
const int XX=99; //XX: infinity ¹«ÇÑ´ë
int touch[MAX]; //¸¶Áö¸· °ÅÄ¡´Â Á¤Á¡
int leng[MAX]; //ÃÖ´Ü °æ·Î ±æÀÌ
int fileopen(int [MAX][MAX¡¦(»ý·«)
|