{"id":1299,"date":"2024-05-13T15:49:44","date_gmt":"2024-05-13T06:49:44","guid":{"rendered":"https:\/\/skanto.co.kr\/?p=1299"},"modified":"2024-05-30T15:40:01","modified_gmt":"2024-05-30T06:40:01","slug":"get-to-know-the-contraction-hierarchy","status":"publish","type":"post","link":"https:\/\/skanto.co.kr\/?p=1299","title":{"rendered":"Get to know the Contraction Hierarchy"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">\uc55e\uc11c \uae38\ucc3e\uae30 \uc54c\uace0\ub9ac\uc998 \uad00\ub828\ud574\uc11c 2\uac1c\uc758 \uc54c\uace0\ub9ac\uc998(Dijkstra, BidirectionalDijkstra)\uc5d0 \ub300\ud574 \uc0b4\ud3b4\ubd24\ub2e4. \ucef4\ud4e8\ud130\ub97c \ud65c\uc6a9\ud558\uc5ec \uae38\uc744 \ucc3e\uc544\uac00\ub294 \uc54c\uace0\ub9ac\uc998\uc758 \ubaa9\uc801\uc740 \ud06c\uac8c \ucd5c\uc801\uc758 \uacbd\ub85c\ub97c \ucd5c\ub300\ud55c \ube68\ub9ac \ucc3e\uc544\ub0b4\ub294 \uac83\uc774\ub77c \ud560 \uc218 \uc788\ub2e4. \uc774\ub860\uc801\uc73c\ub85c \uc774\ub4e4 \uc54c\uace0\ub9ac\uc998\uc740 \ucd5c\uc801\uc758 \uacbd\ub85c\ub97c \ucc3e\uc544\uc8fc\ub294 \uac83\uc744 \ubcf4\uc7a5\ud558\uc9c0\ub9cc \ucd5c\ub300\ud55c \ube68\ub9ac \ucc3e\ub294 \uac83\uc5d0\ub294 \ud55c\uacc4\ub97c \ub4dc\ub7ec\ub0b4\uace0 \uc788\ub2e4. \uc55e\uc5d0\uc11c \uc124\uba85\ud55c BidirectionalDijkstra \uc54c\uace0\ub9ac\uc998\ub3c4 \uc774\ub7f0 \ub9e5\ub77d\uc5d0\uc11c \ud0d0\uc0c9\uc18d\ub3c4\ub97c \uac1c\uc120\ud558\uae30 \uc704\ud55c \ud558\ub098\uc758 \ubc29\ubc95\uc73c\ub85c \ubcfc \uc218 \uc788\ub2e4. \uc774\ucc98\ub7fc Dijkstra Algorithm\uc758 \ud0d0\uc0c9 \uc18d\ub3c4\ub294 \ud0d0\uc0c9\uacf5\uac04 \ud06c\uae30\uc5d0 \uc885\uc18d\uc801\uc77c \uc218 \ubc16\uc5d0 \uc5c6\uc73c\uba70 \ub098\uc544\uac00 \uae38\ucc3e\uae30\uac00 \ud55c \uad6d\uac00\ub97c \ub118\uc5b4 \uae00\ub85c\ubc8c \uaddc\ubaa8\ub85c \ud655\ub300\ud574 \ub098\uac04\ub2e4\uba74 \ud0d0\uc0c9 \uc18d\ub3c4\ub294 \uc11c\ube44\uc2a4 \uacbd\uc7c1\ub825\uc744 \uc720\uc9c0\uc5d0 \uc911\uc694\ud55c \uac78\ub9bc\ub3cc\uc774 \ub420 \uc218\ubc16\uc5d0 \uc5c6\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ucd5c\uadfc\ub4e4\uc5b4 Dijkstra Algorithm\uacfc \uac19\uc774 \uc804\ud1b5\uc801\uc778 \uae38\ucc3e\uae30 \uc54c\uace0\ub9ac\uc998\uc5d0\ub9cc \uc758\uc874\ud558\ub294 \uac83\uc774 \uc544\ub2c8\ub77c \uad50\ud1b5\uacf5\ud559\uc801\uc778 \uc694\uc18c\ub97c \uae38\ucc3e\uae30 \uc54c\uace0\ub9ac\uc998\uc5d0 \uc811\ubaa9\uc2dc\ud0b4\uc73c\ub85c\uc368 \ud0d0\uc0c9\uc18d\ub3c4\ub97c \ud68d\uae30\uc801\uc73c\ub85c \uac1c\uc120\ud558\ub294 \uc2dc\ub3c4\ub4e4\uc774 \uc774\uc5b4\uc9c0\uace0 \uc788\ub2e4. \uadf8 \uc911 \uac00\uc7a5 \ub208\uc5d0 \ub760\ub294 \ubc29\ubc95\uc73c\ub85c \uc774\ubbf8 \uae00\ub85c\ubc8c \ub610\ub294 \uad6d\ub0b4 \ub0b4\ube44 \uc5c5\uccb4\uc5d0\uc11c \ub3c4\uc785\ud558\uace0 \uc788\ub294 \uac83\uc774 Contraction Hierarchy\uc774\ub2e4.  \uc774 \uae00\uc5d0\uc11c\ub294 Contraction Hierarchy\uac00 \uc5b4\ub5a4 \uac1c\ub150\uc744 \uc801\uc6a9\ud558\uace0 \uc788\uc73c\uba70 \uc774\ub807\uac8c \ud568\uc73c\ub85c\uc368 \uc5b4\ub290\uc815\ub3c4\uc758 \uc18d\ub3c4 \ud5a5\uc0c1\uc744 \uc5bb\uc744 \uc218 \uc788\ub294\uc9c0\uc5d0 \ub300\ud574 \uc598\uae30\ud574 \ubcf4\uace0\uc790 \ud55c\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\uacbd\ub85c\ud0d0\uc0c9\uc758 \uc7ac\ud574\uc11d<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\uc55e\uc11c \ubd24\ub4ef\uc774 Dijkstra Algorithm\uc740 \ud558\ub098\uc758 \ucd9c\ubc1c\uc9c0\uc5d0\uc11c\ubd80\ud130 \ub3c4\ub2ec \uac00\ub2a5\ud55c \ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uc5d0 \ub300\ud574 \ucd5c\ub2e8\uacbd\ub85c\ub97c \ucc3e\uc544\ub0b8\ub2e4(SSSP: Single-Source Shortest Path. \ud558\uc9c0\ub9cc \ud604\uc2e4\uc801\uc73c\ub85c \ubd24\uc744 \ub54c \uc6b0\ub9ac\ub294 \uac00\uace0\uc790 \ud558\ub294 \ubaa9\uc801\uc9c0\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uacbd\ub85c\uac00 \uc911\uc694\ud558\uc9c0 \uadf8 \uc678\uc758 \uacbd\ub85c\uc5d0 \ub300\ud574\uc11c\ub294 \uad00\uc2ec\uc774 \uc5c6\ub2e4. \uc989, \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \ucd5c\ub2e8\uacbd\ub85c\uac00 \uad00\uc2ec\uc758 \ub300\uc0c1\uc774\uc9c0 \ud558\ub098\uc758 \ucd9c\ubc1c\uc9c0\uc5d0\uc11c \ub3c4\ub2ec \uac00\ub2a5\ud55c \ubaa8\ub4e0 \uc9c0\uc810\ub4e4\uac04\uc758 \ucd5c\uc801\uacbd\ub85c\ub294 \ubb34\uc758\ubbf8\ud788\ub2e4\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774 \uacbd\uc6b0 Dijkstra Algorithm\uc774 \ud0d0\uc0c9\uacfc\uc815\uc5d0\uc11c \ubaa9\uc801\uc9c0\ub97c \ub9cc\ub0a0 \uacbd\uc6b0 \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud574\ubc84\ub9ac\uba74 \ub354\uc774\uc0c1 \ubd88\ud544\uc694\ud55c \ud0d0\uc0c9\uc744 \uc9c4\ud589\ud558\uc9c0 \uc54a\uc744 \uc218 \uc788\ub2e4. \uc774\ub7f0 \uc0dd\uac01\uae4c\uc9c0 \uc774\uc5b4\uc84c\ub2e4\uba74 Dijkstra Algorithm\uc744 \ud604\uc2e4 \ub3c4\ub85c\uc5d0 \uc801\uc6a9\ud560 \uacbd\uc6b0 \uc5b4\ub290\uc815\ub3c4 \ud6a8\uc728\uc801\uc77c\uae4c\ub77c\ub294 \uc9c8\ubb38\uc744 \ub358\uc9c8 \uc218 \uc788\ub2e4. \uadf8\ub0e5 \ucc98\uc74c \ub4dc\ub294 \uc0dd\uac01\uc740 \ub2e8\uc21c \ubb34\uc2dd\ud55c \ubc29\ubc95(brute-force)\uc774\uc774\ub77c\uace0 \ub290\ub084 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc55e\uc5d0\uc11c \uc124\uba85\ud55c Dijkstra Algorithm\uc5d0\uc11c \ubd24\ub4ef\uc774 \uc5b8\ub73b \ub4dc\ub294 \uc0dd\uac01\uc740 \ubaa9\uc801\uc9c0 \ubc29\ud5a5\uacfc \uad00\ub828\uc774 \uc5c6\ub294(\uc5ed\ubc29\ud5a5) \ub178\ub4dc\ub4e4\uc744 \uad73\uc774 \ucc3e\ub294\ub370 \uc2dc\uac04\uc744 \uc18c\uc694\ud560 \ud544\uc694\uac00 \uc788\uc744\uae4c? \ub610\ub294 \ubaa9\uc801\uc9c0\ub97c \ucc3e\uc544\uac00\ub294\ub370 \uace0\uc18d\ub3c4\ub85c\ub97c \uc774\uc6a9\ud558\ub294 \uac83\uc774 \ud569\ub9ac\uc801\uc774\ub77c\uba74 \uad73\uc774 \ub4b7\uace8\ubaa9 \ub3c4\ub85c\uae4c\uc9c0 \ucc3e\uc544 \uac08 \ud544\uc694\uac00 \uc788\ub098? \ub77c\ub294 \uc0dd\uac01\uc744 \ud558\ub294 \uac83\uc774 \ub2f9\uc5f0\ud558\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc544\ub798\uc640 \uac19\uc774 \ub179\uc0c9\uc73c\ub85c \ud45c\uc2dc\ub41c \ucd9c\ubc1c\uc9c0\uc640 \uc624\ub80c\uc9c0 \uc0c9\uc73c\ub85c \ud45c\uc2dc\ub41c \ubaa9\uc801\uc9c0\ub97c \uac00\uc9c4 \uadf8\ub798\ud504\ub97c \uc0dd\uac01\ud574\ubcf4\uc790.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/dijkstra\/dijkstra-bad.png\" alt=\"\" style=\"width:623px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc774 \uadf8\ub798\ud504\ub97c \ub300\uc0c1\uc73c\ub85c Dijkstra Algorithm\uc744 \uc801\uc6a9\ud55c\ub2e4\uace0 \ud588\uc744 \ub54c \ubaa9\uc801\uc9c0 \uc704\uce58\ub97c \uac10\uc548\ud558\uba74 \ubd89\uc740 \uc0c9 \uc601\uc5ed\uc740 \uad73\uc774 \ud0d0\uc0c9\ud558\uc9c0 \uc54a\uc544\ub3c4 \ub418\uc9c0 \uc54a\uc744\uae4c\ub77c\uace0 \uc0dd\uac01\ud560 \uc218 \uc788\ub2e4. \ub610\ud55c \ub4b7\uace8\ubaa9\uacfc \uac19\uc740 \ub178\ub780\uc0c9\uc758 \uc601\uc5ed\ub3c4 \uad73\uc774 \ud0d0\uc0c9\ud560 \ud544\uc694\uac00 \uc5c6\uc73c\ubbc0\ub85c \ud0d0\uc0c9\uc5d0\uc11c \uc81c\uc678\uc2dc\ud0a4\uace0 \uc2f6\uc744 \uac83\uc774\ub2e4. \uc774\ub807\uac8c \ubcf4\uba74 \ubaa9\uc801\uc9c0\ub85c \ud5a5\ud558\ub294 \uadf8\ub798\ud504\uc0c1\uc5d0\uc11c\ub3c4 <em>dist()<\/em> \uac70\ub9ac \uc810\uc218\uac00 \ub0ae\uc740 \ub178\ub4dc\ub4e4\uc774 \ub9ce\uc774 \uc788\uc744 \uc218 \uc788\ub294\ub370 \uc774\ub7f0 \ub178\ub4dc\ub4e4\uc740 \ucd5c\uc885 \uc0dd\uc131\ub418\ub294 \ucd5c\ub2e8\uacbd\ub85c\uc640 \uad00\ub828\uc131\uc740 \uadf8\ub9ac \ub192\uc9c0\ub294 \uc54a\uc744 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub9cc\uc57d \ub450 \ub178\ub4dc\uc0ac\uc774\uc758 \uc9c0\ub984\uae38\uc744 \uc774\ubbf8 \uc54c\uace0 \uc788\ub294 \uc0c1\ud0dc\ub77c\ub77c\uba74  \uad73\uc774 \ud0d0\uc0c9\uc774 \ud544\uc694\uc5c6\ub294 \uc601\uc5ed\ub4e4\uc740 \uc27d\uac8c \ucc3e\uc544\ub0bc \uc218 \uc788\uc744 \uac83\uc774\ub2e4. \uadf8\ub7ec\ub098 \ub3c4\ub85c\uc758 \uc911\uc694\ub3c4 \uce21\uba74\uc5d0\uc11c \uc5b4\ub5a4 \ub3c4\ub85c(\ub9c1\ud06c)\uac00 \uc5b4\ub5a4 \ub3c4\ub85c\ubcf4\ub2e4 \ub354 \uc911\uc694\ud55c\uc9c0 \uc54c\uc544\ub0b4\ub294 \uac83\uc740 \uace0\uc18d\uc758 Algorithm \uc81c\uc791\uc5d0\uc11c \uc27d\uc9c0 \uc54a\uc740 \uc601\uc5ed\uc774\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\uc99d\uac15\ub41c \uadf8\ub798\ud504 \ubaa8\ub378(Augmented Graph)\uc758 \ud544\uc694\uc131<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\ub3c4\ub85c \ubaa8\ub378\ub9c1\uc5d0 \uc0ac\uc6a9\ub418\ub294 \ubc29\ud5a5\uc131 \uadf8\ub798\ud504(Directed Graph)\ub294 \uc55e\uc5d0\uc11c \uc124\uba85\ud55c \uac1c\ub150\ub4e4\uc744 \ubc18\uc601\ud558\uc9c0 \uc54a\uace0 \uc788\ub2e4. Dijkstra Algorithm\uc740 \uc774\ub860\uc801 \uc99d\uba85\uc744 \ud1b5\ud574 \ucd5c\ub2e8\uacbd\ub85c\ub97c \ucc3e\uc544\uc8fc\uae34 \ud558\uc9c0\ub9cc \ub300\ubd80\ubd84\uc758 \uacbd\uc6b0 \ud544\uc694 \uc774\uc0c1\uc73c\ub85c \uadf8\ub798\ud504\uc758 \ub9ce\uc740 \uc601\uc5ed\uc744 \ud0d0\uc0c9\ud55c\ub2e4. \uc774\ub7f0 \uace0\ubbfc\ub4e4\uc774 \uc313\uc5ec \ub354 \ud6a8\uc728\uc801\uc778 \uacbd\ub85c\ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc744 \uc124\uacc4\ud558\ub294 \uacc4\uae30\ub97c \uc81c\uacf5\ud55c\ub2e4.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\">\ub3c4\ub85c\uc758 \uc911\uc694\ub3c4, \uc704\uce58, \ud0c0\uc785(\ub808\ubca8 \ub4f1)\ub4f1\uc758 \uc815\ubcf4\ub97c \uc5b4\ub5bb\uac8c \uadf8\ub798\ud504\uc5d0 \ubc18\uc601\ud558\uba74 \uacb0\uacfc\uc801\uc73c\ub85c \ud0d0\uc0c9\ubc94\uc704(Search Space)\uac00 \uc904\uc5b4\ub4e4\ub3c4\ub85d \ub9cc\ub4e4 \uc218 \uc788\uc744\uae4c?<\/p>\n<\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">\ubc14\uafd4\ub9d0\ud558\uba74 \uadf8\ub798\ud504\uc5d0\uc11c \uc801\uc740 \uc218\uc758 \ub178\ub4dc\uc640 \ub9c1\ud06c\ub97c \ubc29\ubb38\ud558\uace0\ub3c4 \uac80\uc99d \uac00\ub2a5\ud55c \ucd5c\ub2e8\uacbd\ub85c\ub97c \ucc3e\uc744 \uc218 \uc788\ub2e4\uba74 \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \uacbd\ub85c\ud0d0\uc0c9 \uc18d\ub3c4\ub294 \uadf9\uc801\uc73c\ub85c \ube68\ub77c\uc9c8 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uc5b4\ub290\uc815\ub3c4\uc758 \uc18d\ub3c4\uac1c\uc120\uc774 \uac00\ub2a5\ud560\uae4c?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Contraction Hierarchy Algorithm\uc744 \uc801\uc6a9\ud558\uba74 \uc5b4\ub290\uc815\ub3c4\uc758 \uc18d\ub3c4\uac1c\uc120\uc774 \uac00\ub2a5\ud55c\uc9c0 \ub9db\ubcf4\uae30\ub85c \ubca4\uce58\ub9c8\ud0b9 \uacb0\uacfc\ub97c \ud55c \ubc88 \ubcf4\uc790.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc544\ub798\uc758 \ud45c\ub294 \uc11c\ub85c \ub2e4\ub978 \uc54c\uace0\ub9ac\uc998\uc744 \ud65c\uc6a9\ud558\uc5ec \uc11c\ubd80\uc720\ub7fd\uc758 \ub3c4\ub85c\ub124\ud2b8\uc6cc\ud06c\ub97c \ub300\uc0c1\uc73c\ub85c \uacbd\ub85c\ud0d0\uc0c9\uc744 \ud55c \uacb0\uacfc\uc774\ub2e4. \uc774 \ud45c\ub294 \uc54c\uace0\ub9ac\uc998\uc774 \ud0d0\uc0c9\ud55c \uc815\uc810(vertices, \ub178\ub4dc) \uc218\uc640 \ud0d0\uc0c9\uc2dc\uac04\uc744 \ubcf4\uc5ec\uc900\ub2e4.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>Algorithm<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong># of Scanned Vertices<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>Query Time(microseconds)<\/strong><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">Dijkstra<\/td><td class=\"has-text-align-center\" data-align=\"center\">9326696<\/td><td class=\"has-text-align-center\" data-align=\"center\">2195080 (~ 2 seconds)<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">Contraction Hierarchies<\/td><td class=\"has-text-align-center\" data-align=\"center\">280<\/td><td class=\"has-text-align-center\" data-align=\"center\">110<\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\"><em>\uc54c\uace0\ub9ac\uc998 \uc131\ub2a5\ube44\uad50<\/em><\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\uc6b0\ub9ac\uac00 \uc54c\uace0 \uc788\ub294 Dijkstra Algorithm\uc758 \ud2b9\uc131\uc744 \uac10\uc548\ud558\uba74 \uc55e\uc5d0\uc11c\ub3c4 \uc598\uae30\ud588\ub4ef\uc774 \uc18d\ub3c4\ub97c \uac1c\uc120\ud558\uae30 \uc704\ud574\uc11c\ub294 \ud0d0\uc0c9\uacf5\uac04(Search Space)\uc744 \uc904\uc77c \uc218 \uc788\ub294 \uc815\ubcf4\ub4e4\uc744 \ud65c\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\ub97c \uac1c\uc120\ud558\ub294 \ubc29\ubc95\ubc16\uc5d0 \uc5c6\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7fc \uc774\uc81c \uc18d\ub3c4\uac1c\uc120\uc5d0 \ud65c\uc6a9\ub418\ub294 \uba87\uac00\uc9c0 \uae30\uc220\ubc94\uc8fc\ub97c \uc54c\uc544\ubcf8 \ub2e4\uc74c Contraction Hierarchy\uc758 \uae30\ubc18\uc744 \ub2e4\uc838 \ubcf4\ub3c4\ub85d \ud558\uc790.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\uc18d\ub3c4\uac1c\uc120 \ubc29\ubc95<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\uc18d\ub3c4\uac1c\uc120 \uae30\uc220\uc740 \ud06c\uac8c 2\uac00\uc9c0 \ud615\ud0dc\ub85c \ub098\ub20c \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uc804\ucc98\ub9ac(Preprocessing)<br>\ucd94\uac00\uc801\uc778 \uc815\ubcf4\ub97c \uc774\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\ub97c \ubcc0\ud615\ud55c\ub2e4.<\/li>\n\n\n\n<li>\uc54c\uace0\ub9ac\uc998 Query \uc218\uc815(Modifications to Dijkstra Query)<br>\ud0d0\uc0c9\uacfc\uc815\uc5d0\uc11c \ubd88\ud544\uc694\ud55c \ub178\ub4dc\ub4e4\uc744 \ubc30\uc81c<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Contraction Hierarchy\uc640 \uac19\uc740 \ube60\ub978 \uacbd\ub85c\ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc740 \uc804\ucc98\ub9ac \uacfc\uc815\uc5d0\uc11c \uc0dd\uc131\ub41c \uc815\ubcf4\ub4e4\uc744 \ud65c\uc6a9\ud558\uc5ec \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc758 Query\ub3d9\uc791\uc744 \uc218\uc815\ud558\ub294 \ud615\ud0dc\ub85c \uc811\uadfc\ud55c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uc804\ucc98\ub9ac(Preprocessing)\uc640 Query\uc758 TradeOff<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\ucd5c\uadfc\ub4e4\uc5b4 \uc5ec\ub7ec \uc790\ub8cc\uc5d0\uc11c \uc18d\ub3c4\uac1c\uc120 \uae30\ubc95\uc744 \uc2ec\ub3c4\uc788\uac8c \ub2e4\ub8e8\uace0 \uc788\uc9c0\ub9cc \uc5ec\uae30\uc11c\ub294 \uc911\uc694\ud55c \uac1c\ub150 \uc989, \uc804\ucc98\ub9ac \uc2dc\uac04\uacfc Query \uc2dc\uac04\uc758 tradeoff\uc5d0 \ub300\ud574 \ub2e4\ub8e8\uace0\uc790 \ud55c\ub2e4. \uc55e\uc5d0\uc11c\ub3c4 \uc598\uae30\ud588\uc9c0\ub9cc \uacbd\ub85c\ud0d0\uc0c9\uc758 \ucd5c\uc6b0\uc120 \ubaa9\ud45c\ub294 \uac00\uc7a5 \ube60\ub978 \ud0d0\uc0c9\uc2dc\uac04\uc744 \uc704\ud574 \uc801\uc808\ud55c \ubc29\ubc95\uc73c\ub85c \ud0d0\uc0c9\uacf5\uac04\uc744 \uc904\uc774\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ud55c \uadf9\ub2e8\uc801\uc778 \ubc29\ubc95\uc740 \uc804\ucc98\ub9ac \uacfc\uc815\uc744 \uc774\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\uc758 \ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uac04 \ucd5c\ub2e8\uac70\ub9ac\ub97c \uc0ac\uc804\uc5d0 \uacc4\uc0b0\ud55c \ub2e4\uc74c \ud14c\uc774\ube14 \ud615\ud0dc\ub85c \uc800\uc7a5\ud574 \ub193\uc73c\uba74 \ub41c\ub2e4. \uc774\ub807\uac8c \ud558\uba74 \ucd5c\ub2e8\uac70\ub9ac \ud0d0\uc0c9 \uacfc\uc815\uc774 \ud544\uc694\uc5c6\uc73c\uba70 \ucd5c\uc545\uc758 \uacbd\uc6b0\uc5d0\ub3c4 \uac00\uc7a5 \ube60\ub978 \uc131\ub2a5\uc744 \uc5bb\uc744 \uc218 \uc788\ub2e4. \ubb3c\ub860 \uc804\ucc98\ub9ac \ub2e8\uacc4\uc5d0 \uc18c\uc694\ub418\ub294 \uc2dc\uac04\uc740 6\uc77c \uc774\uc0c1\uc774 \uacb0\ub9b4 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uac00\ub2a5\ud55c \ube60\ub978 \uc804\ucc98\ub9ac \uc2dc\uac04\uc744 \uc6d0\ud55c\ub2e4\uba74 Dijkstra Algorithm\uc744 \uc815\uacf5\ubc95\uc73c\ub85c \uc801\uc6a9\ud558\uba74 \ub41c\ub2e4.  \uc774 \uacbd\uc6b0 \ubaa8\ub450\uac00 \uc608\uc0c1\ud558\ub4ef \uc804\ucc98\ub9ac\uc5d0 \uc18c\uc694\ub418\ub294 \uc2dc\uac04\uc740 \uc5c6\ub2e4. \ub530\ub77c\uc11c \uacbd\ub85c\ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc740 \uc804\ucc98\ub9ac \uc2dc\uac04\uacfc Query \uc2dc\uac04 \uc0ac\uc774\uc5d0\uc11c \uc801\uc808\ud55c \uade0\ud615\uc810\uc744 \ucc3e\uc544\uc57c \ud568\uc744 \uc54c \uc218 \uc788\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/intro\/preprocess-tradeoff.png\" alt=\"\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc704 \uadf8\ub798\ud504\ub294 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \ub300\uc0c1\uc73c\ub85c \uc804\ucc98\ub9ac \uc2dc\uac04\uacfc Query\uc2dc\uac04\uc758 \uc0c1\uac04\uad00\uacc4\ub97c \ubcf4\uc5ec\uc900\ub2e4. Contraction Hierarchy Algorithm\uc774 TradeOff\uad00\uc810\uc5d0\uc11c \uc5b4\ub514\ucbe4 \uc704\uce58\ud558\ub294\uc9c0\ub97c \ubcf4\uc5ec\uc8fc\ub294 \uc815\ub3c4\ub85c \uc0dd\uac01\ud558\uba74 \ub41c\ub2e4. \ud30c\ub780 \uc810\uc73c\ub85c \ud45c\uc2dc\ub41c \uc54c\uace0\ub9ac\uc998\uc740 Contraction Hierarchy\uc5d0 \uc601\ud5a5\uc744 \uc8fc\uac70\ub098 \uc601\ud5a5\uc744 \ubc1b\uc740 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \ubcf4\uba74 \ub41c\ub2e4. \ud29c\ub2dd\uc744 \uc81c\ub300\ub85c \ud55c Contraction Hierarchy\ub294 \uc804\ucc98\ub9ac\uc5d0 \uc18c\uc694\ub418\ub294 \uc2dc\uac04\uc774 \uc57d 5~10\ubd84 \uc815\ub3c4\ub77c\uace0 \ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub7f0 TradeOff\uac00 \uc788\ub2e4\ub294 \uac83\uc744 \uac10\uc548\ud560 \ub54c \uadf8\ub798\ud504 \uac1c\uc120\uc744 \uc704\ud574\uc11c\ub294 \uc591\uc9c8\uc758 \uc815\ubcf4\uac00 \ud544\uc694\ud558\uace0 \ub610\ud55c \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc73c\ub85c \ucc98\ub9ac\ud574\uc57c \ud55c\ub2e4. \uc774\ub7f0 \uce21\uba74\uc5d0\uc11c \ub3c4\ub85c \ub124\ud2b8\uc6cc\ud06c\uc758 \uacc4\uce35\uc801 \ud2b9\uc131\uc744 \uace0\ub824\ud574 \ubcf4\ub294 \uac83\uc740 \uc88b\uc740 \ucd9c\ubc1c\uc810\uc774 \ub420 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">The Hierarchical Nature of Road Networks<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\uc544\ub798\uc758 \uad6c\uae00\ub9f5\uc744 \ubcf4\uba74 \ud2b9\uc815 \uc9c0\uc810(Halligan Hall, the main CS building at Tufts)\uc5d0 \ub9c8\ucee4\uac00 \ucc0d\ud600\uc788\ub2e4. \uc774 \uc9c0\ub3c4 \uc601\uc5ed\uc744 \ud55c \ub2e8\uacc4 \ucd95\uc18c\ud574 \ubcf4\uba74 \uadf8 \ub2e4\uc74c \uc9c0\ub3c4\uc640 \uac19\uc774 \ub41c\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"305\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch1.png\" alt=\"\" class=\"wp-image-1371\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch1.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch1-300x124.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch1-604x251.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"736\" height=\"305\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch2.png\" alt=\"\" class=\"wp-image-1372\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch2.png 736w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch2-300x124.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch2-604x250.png 604w\" sizes=\"auto, (max-width: 736px) 100vw, 736px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc774 \uc0c1\ud0dc\uc5d0\uc11c \uc544\ub798 \uc9c0\ub3c4\uc640 \uac19\uc774 \ud55c\ubc88 \ub354 \ucd95\uc18c\ud558\uba74 \uac00\ub298\uace0 \ud558\uc580\uc0c9\uc774\uc5c8\ub358 \ub3c4\ub85c\uac00 \uc880 \ub450\uaed8\uac00 \uc788\ub294 \ud558\uc580\uc0c9\uc758 \ub3c4\ub85c\uc640 \uc77c\ubd80 \ub178\ub780\uc0c9\uc758 \ub3c4\ub85c\uac00 \ubcf4\uc774\uae30 \uc2dc\uc791\ud560 \uacbb\uc774\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"738\" height=\"308\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch3.png\" alt=\"\" class=\"wp-image-1373\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch3.png 738w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch3-300x125.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch3-604x252.png 604w\" sizes=\"auto, (max-width: 738px) 100vw, 738px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc5ec\uae30\uc11c \uba87 \ubc88 \ub354 \ucd95\uc18c\ub97c \ud558\uac8c \ub418\uba74 \ucd08\uae30 \ud558\uc580\uc0c9\uc774\uc788\ub358 \ub3c4\ub85c\ub294 \uc0ac\ub77c\uc9c0\uace0 \uc5ec\uae30\uc11c \ub354 \ucd95\uc18c\ud574\ubc84\ub9ac\uba74 \ub450\uaebc\uc6e0\ub358 \ud558\uc580\uc0c9 \ub3c4\ub85c\ub3c4 \uc0ac\ub77c\uc9c8 \uac83\uc774\ub2e4. \uc774\ub807\uac8c \uacc4\uc18d\ud574\uc11c  NewYork\uc774 \ubcf4\uc77c \uc815\ub3c4\ub85c \ucd95\uc18c\ud558\uba74 \uc544\ub798 \uc9c0\ub3c4\uc640 \uac19\uc774 \uc774\uc81c \ub450\uaecd\uace0 \ub178\ub780\uc0c9\uc758 \uace0\uc18d\ub3c4\ub85c\ub9cc \ubcf4\uc77c \uac83\uc774\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"736\" height=\"306\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch4.png\" alt=\"\" class=\"wp-image-1374\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch4.png 736w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch4-300x125.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch4-604x251.png 604w\" sizes=\"auto, (max-width: 736px) 100vw, 736px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc704\uc758  \uc124\uba85\uc774 \uc758\ubbf8\ud558\ub294 \ubc14\ub294 \ub3c4\ub85c \ub124\ud2b8\uc6cc\ud06c\uac00 \ub9e4\uc6b0 \uacc4\uce35\uc801\uc73c\ub85c \uad6c\uc131\ub418\uc5c8\uc74c\uc744 \uac15\uc870\ud558\ub294 \uac83\uc774\ub2e4. \uad6c\uae00\ub9f5 \ubfd0\ub9cc \uc544\ub2c8\ub77c \ub2e4\ub978 \uc9c0\ub3c4\ub4e4\ub3c4 \ud655\ub300\/\ucd95\uc18c\ub97c\ud574 \ubcf4\uba74 \uc774\ub7f0 \uac1c\ub150\uc744 \uc798 \uc801\uc6a9\ud558\uace0 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uac00\uae4c\uc6b4 \uac70\ub9ac\uc758 \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \ucd5c\ub2e8\uacbd\ub85c\uc77c \uacbd\uc6b0 \ub450\uaecd\uace0 \ud558\uc580\uc0c9\uc758 \ub3c4\ub85c\uc678\uc5d0 \ucd9c\ubc1c\uc9c0\/\ubaa9\uc801\uc9c0 \uc8fc\ubcc0\uc758 \uc587\uc73c\uba74\uc11c \ud558\uc580\uc0c9\uc758 \ub3c4\ub85c\uc5d0\ub9cc \uad00\uc2ec\uc744 \uac00\uc9c8 \uac83\uc774\ub2e4. \uc704 \uc9c0\ub3c4\uc758 \ucd9c\ubc1c\uc9c0\uc5d0\uc11c New York\uae4c\uc9c0\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub97c \ucc3e\ub294\ub2e4\uba74 \ub300\ubd80\ubd84 \ub178\ub780\uc0c9\uc758 \ub3c4\ub85c\uc5d0 \ub354 \uad00\uc2ec\uc744 \uac00\uc9c8 \uac83\uc774\ub2e4. \uc0ac\uc2e4 \ucd9c\ubc1c\uc9c0\uc5d0\uc11c Philadelphia\uae4c\uc9c0 \uac00\ub294 \ucd5c\ub2e8 \uacbd\ub85c\ub294 \ub300\ubd80\ubd84 \uc774\ub4e4 \ub178\ub780\uc0c9\uc758 \ub3c4\ub85c\ub97c \uc774\uc6a9\ud560 \uac83\uc774\uace0 \uc774\ub4e4 \ub3c4\ub85c\uc758 \ub9ce\uc740 \ubd80\ubd84\uc740 New York\uae4c\uc9c0 \uac00\ub294 \uae38\uacfc \uacb9\uce60 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ucd95\uc18c\ud55c \uc9c0\ub3c4\uc5d0\uc11c\ub294 \ud655\ub300\ub41c \uc9c0\ub3c4\ubcf4\ub2e4 \ub354 \uc801\uc740 \ub178\ub4dc\uc640 Edge(Link)\ub97c \uac00\uc9c0\uc9c0\ub9cc \uc2dc\uac01\ud654\ud574\uc11c \ubcf4\uba74 \ucd5c\ub2e8\uacbd\ub85c\uc0c1\uc5d0\uc11c \uc2e4\uc9c8\uc801\uc73c\ub85c \uc911\uc694\ud55c \ub178\ub4dc\uc640 Edge\uc758 \uc218\ub97c \ud30c\uc545\ud558\ub294\ub370 \ub3c4\uc6c0\uc744 \uc900\ub2e4. \ub2e4\uc2dc\ub9d0\ud574, \ucd08\uae30\uc5d0\ub294 \ub3c4\ub85c\ub124\ud2b8\uc6cc\ud06c\ub97c \uc544\ub798 \uadf8\ub9bc\uacfc \uac19\uc774 \ubaa8\ub378\ub9c1 \ud588\uc5c8\uc9c0\ub9cc<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"731\" height=\"150\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/image.png\" alt=\"\" class=\"wp-image-1376\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/image.png 731w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/image-300x62.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/image-604x124.png 604w\" sizes=\"auto, (max-width: 731px) 100vw, 731px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc55e\uc5d0\uc11c \uad6c\uae00\ub9f5\uc73c\ub85c \uc124\uba85\ud588\ub4ef\uc774 \uadf8\ub798\ud504\uc5d0 \uac1c\ub150\uc801\uc73c\ub85c \ud3ec\ud568\uc2dc\ud0a4\uace0 \uc2f6\uc740 \uc815\ubcf4\ub294 \uc544\ub798\uc640 \uac19\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"731\" height=\"150\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/image-1.png\" alt=\"\" class=\"wp-image-1377\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/image-1.png 731w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/image-1-300x62.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/image-1-604x124.png 604w\" sizes=\"auto, (max-width: 731px) 100vw, 731px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\">\uacc4\uce35\uc801 \uc815\ubcf4\ub97c \uc774\uc6a9\ud558\uba74 \ubb34\uc5c7\uc744 \ud560 \uc218 \uc788\uc744\uae4c?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"> \uc704 \uad6c\uae00\ub9f5\uc758 \uc608\ub85c \ub3cc\uc544\uac00 \ucd9c\ubc1c\uc9c0\uc5d0\uc11c New York\uae4c\uc9c0\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub97c \uc0dd\uac01\ud574\ubcf4\uc790. \ub9e2\uc11c \ub9d0\ud588\ub4ef\uc774 \ub300\ubd80\ubd84\uc758 \ub178\ub780\uc0c9 \ub3c4\ub85c\uc5d0 \uad00\uc2ec\uc744 \uac00\uc9c8 \uac83\uc774\uba70 \uc774\ub294 \uc77c\ubc18\uc801\uc73c\ub85c \uc8fc\ud589\uc0b0 \uac70\ub9ac \ub300\ube44 \uc18c\uc694\uc2dc\uac04\uc774 \uc9e7\uc744 \uac83\uc774\ubbc0\ub85c \uc6d0\uac70\ub9ac \uc5ec\ud589\uc740 \uace0\uc18d\ub3c4\ub85c\ub97c \uc774\uc6a9\ud560 \uac83\uc774\ub77c\uace0 \uc774\ud574\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub610\ud55c \uace0\uc18d\ub3c4\ub85c\uc5d0 \ub4e4\uc5b4\uc11c\uba74 \ubaa9\uc801\uc9c0 \uadfc\ucc98\uc5d0 \ub3c4\ub2ec\ud560 \ub54c\uae4c\uc9c0 \ub418\ub3c4\ub85d\uc774\uba74 \uace0\uc18d\ub3c4\ub85c\ub97c \ubc97\uc5b4\ub098\ub7ec\uace0 \ud558\uc9c0 \uc54a\uc744 \uac83\uc774\ub2e4. \ub2e4\uc2dc\ub9d0\ud574 \uc6d0\uac70\ub9ac\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub97c \uc8fc\ud589\ud558\uba74\uc11c \ub178\ub780\uc0c9\uc758 \ub3c4\ub85c\uc640 \ud558\uc580\uc0c9\uc758 \ub3c4\ub85c\ub97c \uc790\uc8fc \ubc88\uac08\uc544 \uac00\uba74\uc11c \uc774\uc6a9\ud558\uc9c0\ub294 \uc54a\uc744 \uac83\uc774\ub77c\uace0 \uc608\uc0c1\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uac1c\ub150\uc801 \ubaa8\ub378<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\uc81c \ubaa8\ub4e0 \ub3c4\ub85c Edge(\ub9c1\ud06c)\ub4e4\uc5d0 \ub300\ud574 \uc911\uc694\ub3c4(level of importance)\ub97c \uae30\uc900\uc73c\ub85c \ubd84\ub958\ud574\ubcf4\ub294 \uac83\uc744 \uc0dd\uac01\ud574 \ubcfc \uc218 \uc788\ub2e4. \uc608\ub97c \ub4e4\uc5b4 \uace0\uc18d\ub3c4\ub85c\uc758 \uc911\uc694\ub3c4\ub294 \uc774\uba74\ub3c4\ub85c\ubcf4\ub2e4 \ub354 \ub192\ub2e4\uace0 \uc0dd\uac01\ud560 \uc218 \uc788\ub2e4. \uadf8\ub7ec\uba74 \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc5d0 Dijkstra Algorithm\uc744 \uc2e4\ud589\ud560 \ub54c \uc774\uc804 \ub2e8\uacc4\uc5d0\uc11c \ud0d0\uc0c9\ud588\ub358 Edge\ubcf4\ub2e4 \uc911\uc694\ub3c4\uac00 \ub192\uc740 Edge\uc5d0 \uc5f0\uacb0\ub41c \ub178\ub4dc\ub97c \ub300\uc0c1\uc73c\ub85c\ub9cc Heuristic\ud558\uac8c \ud0d0\uc0c9\ud574 \ub098\uac08 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub807\uac8c \ud568\uc73c\ub85c\uc368 \ud0d0\uc0c9\uacfc\uc815\uc5d0\uc11c \ub9ce\uc740 \uc218\uc758 \ub178\ub4dc\ub97c \uc81c\uc678\uc2dc\ud0ac \uc218 \uc788\uc73c\uba70 \ud6a8\uacfc\uc801\uc73c\ub85c \ud0d0\uc0c9\uacf5\uac04\uc744 \uc904\uc77c \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc544\uc9c1\uae4c\uc9c0 Edge\ub4e4\uc744 \ubd84\ub958\ud558\ub294 \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc124\uba85\ud558\uc9c0 \uc54a\uc558\uc73c\ubbc0\ub85c \uc5ec\uae30\uc11c\ub294 \uc774\ub7f0 \uacc4\uce35\uc801 \uac1c\ub150\uc774 Contraction Hierarchy\uc5d0\uc11c \uc0ac\uc6a9\ub418\ub294 \uac1c\ub150\uacfc \ub3d9\uc77c\ud558\ub2e4\ub294 \uc815\ub3c4\ub85c\ub9cc \uc54c\uc544\ub450\uc790.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Contraction Hierarchy\uc758 \uc774\ud574<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\uc591\ubc29\ud5a5 \uacbd\ub85c \ud0d0\uc0c9(\ubcc4\uac1c\uc758 \uc8fc\uc81c\uc784)\uacfc \ub3c4\ub85c\uc758 \uacc4\uce35\uc801 \ud2b9\uc131\uc740 \ud6e8\uc52c \ube60\ub978 \uc54c\uace0\ub9ac\uc998 \uc81c\uc791\uc5d0 \uae30\ubc18\uc774 \ub418\ub294 \uc720\uc6a9\ud55c \uad6c\uc131\uc694\uc18c\ub85c \uc791\uc6a9\ud55c\ub2e4. \uc774 \ub450 \uad6c\uc131\uc694\uc18c\ub97c \uc811\ubaa9\ud568\uc73c\ub85c\uc368 \ud560 \uc218 \uc788\ub294 \uac83\uc73c\ub85c\ub294<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\">(1) <strong>\uc804\ucc98\ub9ac(Preprocess)<\/strong>: \uc77c\uc885\uc758 \uc911\uc694\ub3c4 \uac1c\ub150\uc5d0 \ub530\ub978 Node\uc640 Edge \ubd84\ub958<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">(2) <strong>\ud0d0\uc0c9(Query)<\/strong>: \uc911\uc694\ub3c4\uac00 \ub192\uc740 Edge\ubc29\ud5a5\uc73c\ub85c\ub9cc \uc591\ubc29\ud5a5 \ud0d0\uc0c9 \uc9c4\ud589<\/p>\n<\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub294 \uc911\uc694\ub3c4\uac00 \ub0ae\uc544 \ucd5c\ub2e8\uacbd\ub85c\uc0c1\uc5d0 \ud3ec\ud568\ub418\uc9c0 \uc54a\uc744 \uac83\uc73c\ub85c \uc608\uc0c1\ub418\ub294 \ub9c1\ud06c\ub4e4\uc744 \uadf8\ub798\ud504\uc5d0\uc11c \uc81c\uc678\uc2dc\ucf1c \ub098\uac10\uc73c\ub85c\uc368 \uacb0\uad6d \uc804\uccb4 Edge(\ub9c1\ud06c)\uc758 \uc218\ub97c \uc904\uc778\ub2e4\ub294 \uac83\uc5d0 \uae30\ubc18\uc744 \ub450\uace0\uc788\ub2e4. \uacc4\uce35\uc801 \ub808\ubca8\ub85c \uc774\ub8e8\uc5b4\uc9c4 \ub3c4\ub85c\uac00 \uadf8\ub798\ud504\uc0c1\uc5d0 \ucd5c\uc885 \uacb0\uacfc\ub85c \ub0a8\uac8c \ub420 \uac83\uc774\uba70 \uc774\ub294 \uc591\ubc29\ud5a5 \ud0d0\uc0c9\uc744 \uac00\ub2a5\ud558\uac8c \ud55c\ub2e4. \uadf8\ub7ec\ub098, Node\ub97c \uc904\uc138\uc6b0\uae30 \uc704\ud574 Edge Reduction\ubc29\ubc95\uc744 \uc774\uc6a9\ud560 \uacbd\uc6b0 \ub9ce\uc740 \ube44\uc6a9\uc774 \uc218\ubc18\ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub300\uc2e0, Contraction Hierarchy \uc54c\uace0\ub9ac\uc998\uc740 <strong>Node Contraction<\/strong>\uc744 \uc774\uc6a9\ud558\uc5ec \uacc4\uce35\uc801 \uad6c\uc870\ub97c \ub9cc\ub4e0\ub2e4. \uc5ec\uae30\uc11c \ubaa8\ub4e0 \uac1c\ubcc4 \ub178\ub4dc\ub294 \uac01\uc790 \uace0\uc720\ud55c \uc911\uc694\ub3c4\uc5d0 \uc18d\ud558\uac8c \ub41c\ub2e4.(\ub2e4\uc2dc \ub9d0\ud574 \uc911\uc694\ub3c4\uc5d0 \ub530\ub978 \ub178\ub4dc\uc758 \uc815\ub82c\uc774\ub77c \ud560 \uc218 \uc788\uc74c)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Contraction\uacfc\uc815\uc744 \uac70\uce58\uba74 \uc77c\ub828\uc758 \uc9c0\ub984\uae38 Edge(shortcut edge)\uac00 \uadf8\ub798\ud504\uc5d0 \ucd94\uac00\ub418\uace0 \uc720\uc9c0\ub41c\ub2e4. \uc774\ud6c4 \uc591\ubc29\ud5a5 \ud0d0\uc0c9\uacfc\uc815\uc5d0\uc11c \uc911\uc694\ub3c4\uac00 \ub0ae\uc740 \ub2e8\uacc4\uc5d0\uc11c\ubd80\ud130 \ub192\uc740 \ub2e8\uacc4\uc758 Node\ub85c \uc774\uc5b4\uc9c0\ub294 Edge\ub9cc\uc744 \ub300\uc0c1\uc73c\ub85c \ud0d0\uc0c9\uc744 \ud558\uba70 \uc774\ub4e4 Edge\ub4e4 \uc911\uc5d0\ub294 \uc9c0\ub984\uae38 Edge\ub3c4 \ud3ec\ud568\ub420 \uc218\ub3c4 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uacb0\uacfc\uc801\uc73c\ub85c CH \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud55c \uac1c\uad04\uc801\uc778 \uc124\uba85\uc740 \uc544\ub798\uc640 \uac19\uc774 \uae30\uc220\ud560 \uc218 \uc788\ub2e4. \uadf8\ub9ac\uace0 \uc774\ud6c4 \ub0b4\uc6a9\uc5d0\uc11c \ud575\uc2ec \uc694\uc18c\uc5d0 \ub300\ud55c \uc0c1\uc138\ud55c \uc124\uba85\uc744 \uc774\uc5b4\ub098\uac00\ub3c4\ub85d \ud558\uaca0\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uac70\uc2dc\uc801 \uad00\uc810\uc758 CH Algorithm:<\/h3>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\"><strong>Preprocess<\/strong>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uc911\uc694\ub3c4 \ub808\ubca8\uc5d0 \ub530\ub978 Node \uc904\uc138\uc6b0\uae30<\/li>\n\n\n\n<li>\uac00\uc7a5 \ub35c \uc911\uc694\ud55c \ub178\ub4dc\uc5d0\uc11c \uac00\uc7a5 \uc911\uc694\ud55c \ub178\ub4dc \uc21c\uc73c\ub85c Contraction \uc218\ud589<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Query<\/strong>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uc591\ubc29\ud5a5 Dijkstra \ud0d0\uc0c9\uc744 \uc801\uc6a9\ud558\uba70 \uc774\ub54c \uc911\uc694\ub3c4\uac00 \ub192\uc740 \ub178\ub4dc\ub85c \uc774\uc5b4\uc9c0\ub294 Edge\ub9cc\uc744 \ud0d0\uc0c9 \ub300\uc0c1\uc73c\ub85c \ud568<\/li>\n<\/ul>\n<\/blockquote>\n\n\n\n<h2 class=\"wp-block-heading\">Node Contraction<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\ud558\ub098\uc758 Node\ub97c \ucd95\uc18c(Contract)\ud560 \ub54c \uba3c\uc800 \ub300\uc0c1\uc774 \ub418\ub294 Node\ub97c \uadf8\ub798\ud504\uc5d0\uc11c \uc81c\uc678\uc2dc\ud0a8\ub2e4. \ub9cc\uc57d Contraction \uc804\uc5d0 \uc81c\uc678\ub41c Node\uac00 \uc774\uc6c3\ud558\ub294 \ub450 \ub178\ub4dc \uc0ac\uc774\uc758 \ucd5c\ub2e8\uacbd\ub85c\uc0c1\uc5d0 \uc704\uce58\ud558\uace0 \uc788\ub2e4\uba74 \uc774\ub4e4 \ub450 \uc774\uc6c3 Node\uc0ac\uc774\uc5d0 \uc9c0\ub984\uae38(shortcut) Edge\ub97c \ucd94\uac00\ud55c\ub2e4. \uc774\ub54c \ucd5c\ub2e8\uacbd\ub85c\uc0c1\uc758 \uac70\ub9ac(\ucd5c\ub2e8\uac70\ub9ac)\ub294 \uc9c0\ub984\uae38 Edge\uc5d0 \uc720\uc9c0\ub418\ub3c4\ub85d \ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uac04\ub2e8\ud55c \uc608\ub97c \ub4e4\uc5b4\ubcf4\uc790. \uc544\ub798 \uadf8\ub9bc\uc5d0\uc11c Node v\ub97c \uc81c\uc678\uc2dc\ud0a4\uba74 2\uac1c\uc758 Edge\ub97c \uc81c\uc678\ud558\uace0  v, p, q, r \uc0ac\uc774\uc758 Edge\ub294 \ubaa8\ub450 \uc0ac\ub77c\uc9c0\uac8c \ub41c\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"733\" height=\"293\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch5.png\" alt=\"\" class=\"wp-image-1387\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch5.png 733w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch5-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch5-604x241.png 604w\" sizes=\"auto, (max-width: 733px) 100vw, 733px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"295\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch6.png\" alt=\"\" class=\"wp-image-1388\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch6.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch6-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch6-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uba3c\uc800 Node v\uc640 \uc778\uc811\ud558\uace0 \uc788\ub294 Edge\ub4e4\uc744 \uadf8\ub798\ud504\uc5d0\uc11c \uc81c\uc678\uc2dc\ud0a8\ub2e4. \uadf8\ub7f0 \ub2e4\uc74c v\uc640 \uc774\uc6c3\ud558\uace0 \uc788\ub294 \ub450 \ub178\ub4dc \uc0ac\uc774\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub4e4 \uc911 v\ub97c \uc9c0\ub098\uac00\ub294 \ucd5c\ub2e8\uacbd\ub85c\uac00 \uc874\uc7ac\ud558\ub294\uc9c0 \ud655\uc778\ud55c\ub2e4. \uc774 \uc608\uc81c\uc5d0\uc11c\ub294, p\uc640 r, q\uc640 r, p\uc640 q\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub294 \ubaa8\ub450 v\ub97c \uc9c0\ub098\uac04\ub2e4. \ub530\ub77c\uc11c \uc9c0\ub984\uae38 Edge pr, qr, pq\ub97c \ucd94\uac00\ud55c\ub2e4. \uc774\ub54c \uc9c0\ub984\uae38 Edge\uc758 weight\ub294 contract\ub41c \ub9c1\ud06c\uc758 weight\ub97c \ub354\ud55c \uac12(\ucd5c\ub2e8\uac70\ub9ac)\uc73c\ub85c \uc124\uc815\ud55c\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"295\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch7.png\" alt=\"\" class=\"wp-image-1389\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch7.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch7-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch7-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\ub178\ub4dc v\uc640 \uc778\uc811\ud558\uace0 \uc788\ub294 Edge\ub4e4\uc744 \uc81c\uc678\uc2dc\ucf30\uc744 \ub54c q\uc5d0\uc11c r\ub85c \uc774\uc5b4\uc9c0\ub294 \uacbd\ub85c\uac00 \ube44\ub85d \uc874\uc7ac\ud558\ub354\ub77c\ub3c4 q\uc640 r\uc0ac\uc774\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub294 \uc544\ub2c8\ubbc0\ub85c \uc9c0\ub984\uae38 Edge qr\uc740 \ud544\uc694\ud55c \uc0c1\ud669\uc774 \ub41c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uc77c\ubc18\uc801 \uc815\uc758(Formal Definition)<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Node v\ub85c \uc778\uc785\ud558\ub294 \ubaa8\ub4e0 Edge\uc758 \uc2dc\uc791(from) \uc815\uc810(vertices, node)\ub4e4\ub85c \uad6c\uc131\ub41c \uc9d1\ud569\uc744 U\ub77c \ud558\uace0 Node v\uc5d0\uc11c \ubed7\uc5b4\ub098\uac00\ub294 Edge\uc5d0 \ub300\uc751\ud558\ub294 \ub05d(to) \uc815\uc810\ub4e4\ub85c \uad6c\uc131\ub41c \uc9d1\ud569\uc744 W\ub77c\uace0 \ud560 \ub54c<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">U\uc9d1\ud569\uc758 \ud55c \uc6d0\uc18c\uc778 u\uc640 W\uc9d1\ud569\uc758 \ud55c \uc6d0\uc18c\uc778 w\uc778 \uac01 \uc815\uc810\ub4e4\uc758 \uc30d(v, w)\uc5d0 \ub300\ud574<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\">\ub9cc\uc57d \uacbd\ub85c &lt;uvw&gt;\uac00 u\uc5d0\uc11c w\ub85c \uac00\ub294 \uc720\uc77c\ud55c \ucd5c\ub2e8\uacbd\ub85c\uc77c \uacbd\uc6b0 \uc9c0\ub984\uae38 Edge uw\ub97c \uadf8\ub798\ud504\uc5d0 \ucd94\uac00\ud55c\ub2e4. \uc774\ub54c \uc9c0\ub984\uae38 Edge\uc758 weight\ub294 w(u, v) + w(v, w)\ub85c \ud55c\ub2e4.<\/p>\n<\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7f0 \ub2e4\uc74c \ub178\ub4dc v\uc5d0 \uc778\uc811\ud55c \ubaa8\ub4e0 Edge\ub4e4\uc744 \uadf8\ub798\ud504\uc5d0\uc11c \uc81c\uc678\uc2dc\ud0a8\ub2e4. \uc774\ub807\uac8c \ud558\uba74 Node v\uc5d0 \ub300\ud55c Contraction\uc774 \uc885\ub8cc\ub41c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uc744 \uc0c1\ub300\ub85c\ud55c Contraction<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc55e\uc5d0\uc11c \uc124\uba85\ud55c Node Contraction\uc744 \uac10\uc548\ud558\uba74 CH\uc54c\uace0\ub9ac\uc998\uc740 Node\uac04\uc758 \ud2b9\uc815 \uc21c\uc11c\ub97c \uae30\ubc18\uc73c\ub85c \uac01 Node\ub4e4\uc744 Contraction\ud558\uace0 \uc788\uc74c\uc744 \uc2dc\uc0ac\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc9c0\uae08\uc740 \uc774 Node\ub4e4 \uac04\uc758 \uc21c\uc11c\uac00 \uc774\ubbf8 \uc815\ud574\uc838 \uc788\ub2e4\uace0 \uac00\uc815\ud558\uc790. \uace7 \uc54c\uac8c \ub418\uaca0\uc9c0\ub9cc \uc88b\uc740 Node Ordering(\uc21c\uc11c) \ubd80\uc5ec\ub294 \uace0\uc18d CH\uc54c\uace0\ub9ac\uc998\uc5d0\uc11c \uac00\uc7a5 \ud575\uc2ec\uc801\uc778 \ubd80\ubd84\ub97c \ucc28\uc9c0\ud55c\ub2e4. \uadf8\ub807\uc9c0\ub9cc \uc21c\uc11c\uac00 \uc784\uc758\ub85c \ubd80\uc5ec\ub41c\ub2e4 \ud558\ub354\ub77c\ub3c4 \uc591\ubc29\ud5a5 \ud0d0\uc0c9\uc740 \uc815\uc0c1\uc801\uc73c\ub85c \ub3d9\uc791\ud55c\ub2e4\ub294 \uac83\uc744 \uc99d\uba85\ud574 \ubcfc \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc21c\uc11c\uc5d0 \ub530\ub978 Node Contraction\uc744 \uc124\uba85\ud558\uae30 \uc704\ud574 \uc784\uc758\uc758 \uc911\uc694\ub3c4 \ub808\ubca8\uc5d0 \ub530\ub77c Node\ub4e4\uc744 \uc0ac\uc804\uc5d0 \uc904\uc138\uc6cc \ub1a8\ub2e4\uace0 \uc0dd\uac01\ud574\ubcf4\uc790.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7f0 \ub2e4\uc74c [1, n]\uc73c\ub85c \uc774\uc5b4\uc9c0\ub294 \uac01 \ucc98\ub9ac \ub2e8\uacc4 i \uc5d0\uc11c \uc815\uc810(Vertex, Node) <em>v<sub>i<\/sub><\/em> \uc640 \uc778\uc811\ud558\uace0 \uc788\ub294 \ubaa8\ub4e0 Edge\ub4e4\uc744 \uadf8\ub798\ud504\uc5d0\uc11c \uc81c\uc678\uc2dc\ud0b4\uc73c\ub85c\uc368 \uc815\uc810 <em>v<sub>i<\/sub><\/em> \ub97c contract \uc2dc\ud0a8\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">i + 1\ubc88\uc9f8 \ub2e8\uacc4\uc758 \uadf8\ub798\ud504\uc5d0\ub294 n &#8211; i \uac1c\uc218\uc758 \ub178\ub4dc\ub9cc \ub0a8\uac8c \ub41c\ub2e4. \ud558\uc9c0\ub9cc \uadf8\ub798\ud504\uc5d0\ub294 \uc774 \uc804\ub2e8\uacc4\uc5d0\uc11c \ucd94\uac00\ub41c \uc9c0\ub984\uae38 Edge\ub4e4\ub3c4 \uac19\uc774 \ud3ec\ud568\ub418\uac8c \ub41c\ub2e4. \uc9c0\ub984\uae38 Edge\uc640 \uc778\uc811\ud55c Node\uac00 Contract\ub420 \uacbd\uc6b0\uc5d0\ub3c4 \uc774 \uc9c0\ub984\uae38 Edge\ub97c \ub3d9\uc77c\ud55c \ubc29\ubc95\uc73c\ub85c \uadf8\ub798\ud504\uc5d0\uc11c \uc81c\uc678(contract)\uc2dc\ucf1c \ub098\uac04\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\ub367\ub304 \uadf8\ub798\ud504(The Overlay Graph)<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\ub178\ub4dc <em>v<sub>n<\/sub><\/em> \uae4c\uc9c0 Contract\ud558\uace0 \ub098\uba74 \ucd08\uae30\uc5d0 \uc788\uc5c8\ub358 \ubaa8\ub4e0 Node\uc640 Edge \uadf8\ub9ac\uace0 Contraction \uacfc\uc815\uc5d0\uc11c \ucd94\uac00\ub41c \ubaa8\ub4e0 \uc9c0\ub984\uae38 Edge\ub4e4\uc744 \ud3ec\ud568\ud558\ub294 \uadf8\ub798\ud504\uc778 G*\ub97c \uc0dd\uac01\ud560 \uc218 \uc788\ub2e4. \uc774 \uadf8\ub798\ud504 G* \ub97c \uc591\ubc29\ud5a5 Dijkstra \ud0d0\uc0c9\uc5d0 \ud65c\uc6a9\ud55c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Example<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\ubaa8\ub4e0 Node\ub4e4\uc758 Contraction \uacfc\uc815\uc744 \uc2dc\uac01\ud654\ud558\uae30 \uc704\ud574 \uc544\ub798\uc640 \uac19\uc774 \uc784\uc758\uc758 Node\uc21c\uc11c\ub85c \uad6c\uc131\ub41c \uadf8\ub798\ud504\ub97c \uc0dd\uac01\ud574\ubcf4\uc790.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"296\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch8.png\" alt=\"\" class=\"wp-image-1395\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch8.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch8-300x121.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch8-604x243.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc774 \uadf8\ub798\ud504\uc758 Contraction\uacfc\uc815\uc744 \uc21c\uc11c\ub300\ub85c \ud45c\ud604\ud558\uba74 \uc544\ub798\uc640 \uac19\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"734\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch9.png\" alt=\"\" class=\"wp-image-1396\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch9.png 734w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch9-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch9-604x242.png 604w\" sizes=\"auto, (max-width: 734px) 100vw, 734px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch10.png\" alt=\"\" class=\"wp-image-1397\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch10.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch10-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch10-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"734\" height=\"295\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch11.png\" alt=\"\" class=\"wp-image-1398\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch11.png 734w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch11-300x121.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch11-604x243.png 604w\" sizes=\"auto, (max-width: 734px) 100vw, 734px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"734\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch12.png\" alt=\"\" class=\"wp-image-1399\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch12.png 734w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch12-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch12-604x242.png 604w\" sizes=\"auto, (max-width: 734px) 100vw, 734px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"734\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch13.png\" alt=\"\" class=\"wp-image-1401\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch13.png 734w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch13-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch13-604x242.png 604w\" sizes=\"auto, (max-width: 734px) 100vw, 734px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch14.png\" alt=\"\" class=\"wp-image-1402\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch14.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch14-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch14-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"736\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch15.png\" alt=\"\" class=\"wp-image-1403\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch15.png 736w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch15-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch15-604x241.png 604w\" sizes=\"auto, (max-width: 736px) 100vw, 736px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"734\" height=\"296\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch16.png\" alt=\"\" class=\"wp-image-1404\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch16.png 734w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch16-300x121.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch16-604x244.png 604w\" sizes=\"auto, (max-width: 734px) 100vw, 734px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"733\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch17.png\" alt=\"\" class=\"wp-image-1405\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch17.png 733w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch17-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch17-604x242.png 604w\" sizes=\"auto, (max-width: 733px) 100vw, 733px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"733\" height=\"293\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch18.png\" alt=\"\" class=\"wp-image-1406\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch18.png 733w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch18-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch18-604x241.png 604w\" sizes=\"auto, (max-width: 733px) 100vw, 733px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"295\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch19.png\" alt=\"\" class=\"wp-image-1407\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch19.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch19-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch19-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"295\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch20.png\" alt=\"\" class=\"wp-image-1408\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch20.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch20-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch20-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc774 Contraction \uacfc\uc815\uc744 \ud1b5\ud574 \uc544\ub798\uc640 \uac19\uc774 \ucd5c\uc885\uc801\uc73c\ub85c \ub9cc\ub4e4\uc5b4\uc9c4 G* Overlay \uadf8\ub798\ud504\ub97c \uc2dc\uac01\ud654 \ud560 \uc218 \uc788\ub2e4. \uc774 \uadf8\ub798\ud504\uc5d0\ub294 \ucd08\uae30\uc758 \uadf8\ub798\ud504\uc778 G\uc640 Contraction\uacfc\uc815\uc5d0\uc11c \ucd94\uac00\ub41c 3\uac1c\uc758 \uc9c0\ub984\uae38 Edge\uac00 \uac19\uc774 \ud3ec\ud568\ub41c\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/contraction\/g-star-graph.png\" alt=\"\" style=\"width:726px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc774 \uadf8\ub798\ud504\uc5d0\uc11c \uc9c0\ub984\uae38 Edge\ub4e4\uc740 \ucd5c\ub2e8\uac70\ub9ac\ub97c \uc720\uc9c0\ud558\uace0 \uc788\uc74c\uc744 \ud655\uc778\ud560 \uc218 \uc788\ub2e4. \ub610\ud55c, Node\uc758 Contraction \uc21c\uc11c\ub97c \ubc14\uafbc\ub2e4\uba74 \uc11c\ub85c \ub2e4\ub978 \ud615\ud0dc\uc758 \uc9c0\ub984\uae38 Edge\ub4e4\uc774 \ub9cc\ub4e4\uc5b4\uc9c8 \uc218 \uc788\ub2e4. (\ucd94\ud6c4\uc5d0 \ub2e4\uc2dc \ub2e4\ub8f0 \uc608\uc815)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ud558\uc9c0\ub9cc \ub2f9\ubd84\uac04\uc740 \uc9c0\uae08 \uc801\uc6a9\ud55c Node Ordering\uc774 \ub2e8\uc9c0 3\uac1c\uc758 \uc9c0\ub984\uae38 Edge\ub9cc \ucd94\uac00\ud588\uc73c\ubbc0\ub85c \ube44\uad50\uc801 \uc88b\uc740 Ordering\ub77c\uace0 \uc0dd\uac01\ud558\uc790.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\ucd94\uac00\ud560 \uc9c0\ub984\uae38\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \uacc4\uc0b0\ud558\ub294 \ubc29\ubc95<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc55e\uc5d0\uc11c \uc608\ub85c \ub4e0 \uadf8\ub798\ud504\ub294 \ub208\uc73c\ub85c \ub300\ucda9 \ubd10\ub3c4 Contract\ub420 Node\uac00 \uc774\uc6c3\ud558\ub294 \ub450 Node\ub4e4 \uc0ac\uc774\uc5d0\uc11c \ucd5c\ub2e8\uacbd\ub85c\uc778\uc9c0 \uc27d\uac8c \uc54c\uc544\ubcfc \uc218 \uc788\ub2e4. \ud558\uc9c0\ub9cc \uc77c\ubc18\uc801\uc73c\ub85c \uc9c0\ub984\uae38 Edge\ub97c \ucd94\uac00\ud560 \ub54c \ud6a8\uc728\uc801\uc778 \uc9c0\ub984\uae38 \ud310\ubcc4 \ubc29\ubc95\uc774 \ud544\uc694\ud558\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\uc9c0\ub984\uae38 \ucd94\uac00(Adding Shortcuts)<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\ubcf5\uae30\ud574\ubcf4\uc790\uba74, Node v\ub97c Contract\ud558\ub824\uace0 \ud560 \ub54c v\ub85c \uc778\uc785\ud558\ub294 Edge(\ub9c1\ud06c)\uc758 from\ucabd Vertex(\ub178\ub4dc)\ub4e4\uc758 \uc9d1\ud569\uc744 U, v\ub85c\ubd80\ud130 \ubed7\uc5b4 \ub098\uac00\ub294 Edge\uc758 to \ucabd\uc5d0 \uc788\ub294 Vertex\ub4e4\uc758 \uc9d1\ud569\uc744 W\ub77c\uace0 \ud560 \ub54c \uc9d1\ud569 U\uc5d0 \uc18d\ud574\uc788\ub294 \ub178\ub4dc u\uc640 \uc9d1\ud569 V\uc5d0 \uc18d\ud574\uc788\ub294 \ub178\ub4dc v\uac00 \uc788\uc744 \uacbd\uc6b0 \uacbd\ub85c &lt;uvw&gt;\uac00 u\uc5d0\uc11c w\ub85c \uac00\ub294 \ucd5c\ub2e8\uacbd\ub85c\uc77c \uacbd\uc6b0\uc5d0\ub9cc \uc9c0\ub984\uae38 Edge uw\ub97c \ucd94\uac00\ud55c\ub2e4\uace0 \ud588\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uc9c1\uad00\uc801 \uc811\uadfc(A straightforward approach)<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc5b4\ub5a4 \uc9c0\ub984\uae38\uc774 \ud544\uc694\ud55c\uc9c0 \ubc14\ub85c \uc54c\uc544 \ubcf4\ub824\uba74 \uc9d1\ud569 U\uc5d0 \uc788\ub294 \ubaa8\ub4e0 \ub178\ub4dc u\uc5d0 \ub300\ud574 v\ub97c \uc81c\uc678\ud55c \uc0c1\ud0dc\uc5d0\uc11c \uc9c0\uc5fd\uc801(local) \ucd5c\ub2e8\uacbd\ub85c \ud0d0\uc0c9\uc744 \ud574\ubcf4\uba74 \ub41c\ub2e4. \ub9cc\uc57d w(u v) + w(v, w) \ubcf4\ub2e4 \uc9e7\uc740 \uac70\ub9ac\ub85c \uc9d1\ud569 W\uc5d0 \uc788\ub294 \ub178\ub4dc w\uc5d0 \ub3c4\ub2ec\ud560 \uc218 \uc788\ub2e4\uba74 \uc0c8\ub85c\uc6b4 \ucd5c\ub2e8\uacbd\ub85c\ub97c \ucc3e\uc558\uc73c\ubbc0\ub85c(witnessing) \uacbd\ub85c <em>&lt;uvw><\/em>\ub294 \uc774\uc81c u\uc5d0\uc11c w\ub85c \uac00\ub294 \ucd5c\uc801\uacbd\ub85c\uac00 \uc544\ub2cc \uc0c1\ud0dc\uac00 \ub41c\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/shortcuts\/example-1.png\" alt=\"\" style=\"width:562px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\ub2e4\ub974\uac8c \ubcf4\uba74, \uacbd\ub85c &lt;uvw>\uac00 u\uc5d0\uc11c w\ub85c \uac00\ub294 \ucd5c\ub2e8\uac70\ub9ac\uc774\uba74\uc11c \uc720\uc77c\ud55c \uacbd\ub85c\uc77c \uacbd\uc6b0 v\ub97c \uc81c\uc678\ud55c \uc0c1\ud0dc\uc758 \uc11c\ube0c\uadf8\ub798\ud504\ub3c4 \uace0\ub824\ud574\uc57c \ud558\ubbc0\ub85c local \ud0d0\uc0c9\uc740 \uacc4\uc18d \uc774\uc5b4\ub098\uac08 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub530\ub77c\uc11c \uc9d1\ud569 U\uc758 \uc18d\ud55c \ubaa8\ub4e0 \uac1c\ubcc4 \ub178\ub4dc u\uc5d0 \ub300\ud574 \uc544\ub798\uc758 \uacfc\uc815\uc744 \uc218\ud589\ud55c\ub2e4.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<ol class=\"wp-block-list\">\n<li>\uc9d1\ud569 W\uc5d0 \uc18d\ud55c \ubaa8\ub4e0 \ub178\ub4dc w\uc5d0 \ub300\ud574 v\ub97c \uac70\uccd0 u\uc5d0\uc11c w\ub85c \uac00\ub294 \uacbd\ub85c\uc758 cost\uc778 P<sub>w<\/sub> \ub97c \uacc4\uc0b0\ud55c\ub2e4. \uc774 \uac12\uc740 \ub450 Edge \uc758 \ud569\uc774 \ub41c\ub2e4: <em>w(u, v) + w(v, w)<\/em><\/li>\n\n\n\n<li>P<sub>max<\/sub>\ub294 \uc9d1\ud569 W\uc758 \ubaa8\ub4e0 \ub178\ub4dc w\ub4e4\uc758 P<sub>w<\/sub> \uc911\uc5d0\uc11c \ucd5c\ub300\uac12\uc744 \ub098\ud0c0\ub0b8\ub2e4.<\/li>\n\n\n\n<li>v\ub97c \uc81c\uc678\uc2dc\ud0a8 \uc0c1\ud0dc\uc758 \uadf8\ub798\ud504\uc5d0\uc11c u\ub97c \uc2dc\uc791\uc810\uc73c\ub85c \ud558\ub294 \ud45c\uc900 Dijkstra \ud0d0\uc0c9\uc744 \uc218\ud589\ud55c\ub2e4.<\/li>\n\n\n\n<li>\ud0d0\uc0c9\uacfc\uc815\uc5d0\uc11c \ubc29\ubb38\ud55c Node\uc758 \ucd5c\ub2e8\uac70\ub9ac\uac00 P<sub>max&#8217;<\/sub>\ubcf4\ub2e4 \ud074 \uacbd\uc6b0 \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud55c\ub2e4.<\/li>\n<\/ol>\n<\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7f0 \ub2e4\uc74c Dijkstra \ud0d0\uc0c9\uc744 \ud1b5\ud574 \uc5bb\uc740 v\ub97c \uac70\uce58\uc9c0 \uc54a\uc73c\uba74\uc11c \uac01 w\uc5d0 \uc774\ub974\ub294 \ucd5c\ub2e8\uac70\ub9ac\uac00 P<sub>w<\/sub>\ubcf4\ub2e4 \ud06c\ub2e4\uba74 \uc989, <em>dist(u, w) > P<sub>w<\/sub><\/em>\ub97c \ub9cc\uc871\ud558\uba74 \uc9c0\ub984\uae38 Edge\uc778 uw\ub97c \ucd94\uac00\ud558\uace0 \ucd5c\ub2e8\uac70\ub9ac(weight)\ub294 Pw&#8217;\uac00 \ub418\ub3c4\ub85d \uc124\uc815 \ud55c\ub2e4. \uc774 \uc870\uac74\uc744 \ub9cc\uc871\ud558\uc9c0 \ubabb\ud55c\ub2e4\uba74 \uc9c0\ub984\uae38 Edge\ub294 \ucd94\uac00\ud558\uc9c0 \uc54a\ub294\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uac80\uc99d(Correctness)<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc55e\uc5d0\uc11c\uc758 \uc124\uba85\uc740 Dijkstra \ud0d0\uc0c9\uc73c\ub85c \ubc29\ubb38\ud55c(settled) \ub178\ub4dc\uc758 \ucd5c\ub2e8\uac70\ub9ac\uac00 P<sub>max&#8217;<\/sub>\ubcf4\ub2e4 \ud074 \uacbd\uc6b0 \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud55c\ub2e4\uace0 \ud588\ub2e4. \uadf8\ub7ec\uba74 \uc9d1\ud569 U\uc5d0 \uc18d\ud574 \uc788\ub294 \ub178\ub4dc u\uc5d0 \ub300\ud574 \uc9d1\ud569 W\uc758 \ub178\ub4dc w\uae4c\uc9c0\uc758 \ucd5c\ub2e8\uacbd\ub85c\uac00 \uc874\uc7ac\ud55c\ub2e4\uba74 \uc774 \uacbd\ub85c\uc758 \uae38\uc774\ub294 P<sub>w&#8217;<\/sub>\ubcf4\ub2e4 \uc791\uc73c\uba70<em>(P<sub>w&#8217;<\/sub>\uac00 v\ub97c \uc9c0\ub098\uac00\ub294 w&#8217;\uc73c\ub85c \uac00\ub294 \ucd5c\ub2e8\uacbd\ub85c\ub85c \uc778\uc9c0\ud558\uace0 \uc788\uc73c\ubbc0\ub85c)<\/em> \uacb0\uacfc\uc801\uc73c\ub85c P<sub>max&#8217;<\/sub>\ubcf4\ub2e4 \uc791\uac70\ub098 \uac19\ub2e4\ub77c\uace0 \ud560 \uc218 \uc788\ub2e4. \ub530\ub77c\uc11c, \ucd5c\ub2e8\uac70\ub9ac\uac00 P<sub>max&#8217;<\/sub>\ubcf4\ub2e4 \ucee4\uc9c8 \uacbd\uc6b0 \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud55c\ub2e4\ub294 \uc870\uac74\uc740 \ub178\ub4dc u\uc5d0\uc11c \uc2dc\uc791\ub418\ub294 local \ud0d0\uc0c9 \uacfc\uc815\uc5d0\uc11c \ubc29\ubb38\ud55c \ubaa8\ub4e0 w\uc758 \ucd5c\ub2e8\uac70\ub9ac dist(u, w)\uac00 \ub3c4\ucd9c\ub418\uc5c8\uc74c\uc744 \uc720\ucd94\ud560 \uc218 \uc788\ub2e4. \uc544\ub798 \uc608\uc81c\ub97c \uc0b4\ud3b4\ubcf4\uc790.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/shortcuts\/correctness-1.png\" alt=\"\" style=\"width:567px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc5ec\uae30\uc11c u3\uc5d0\uc11c \uc2dc\uc791\ud558\ub294 local Dijkstra\ud0d0\uc0c9\uc744 \uc218\ud589\ud560 \uacbd\uc6b0 P<sub>max<\/sub>\ub294 12\uac00 \ub41c\ub2e4. \ub530\ub77c\uc11c u3\uc640 w2\uc0ac\uc774\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub97c \ub098\ud0c0\ub0b4\ub294 \ube68\uac04\uc0c9 edge\ub294 \ud0d0\uc0c9\uc774 \uc885\ub8cc\ub418\uae30 \uc804\uc5d0 \uac31\uc2e0(relax)\ub41c\ub2e4. \uc774 \uacbd\uc6b0 u3\uc640 w2\uc0ac\uc774 \ucd5c\ub2e8\uac70\ub9ac\uac00 8\uc774\ub418\uba70 v\ub97c \uc9c0\ub098\uac00\ub294 \uacbd\ub85c\uc758 \uac70\ub9ac 9\ubcf4\ub2e4 \uc791\uc73c\ubbc0\ub85c \uc9c0\ub984\uae38 Edge\ub294 \ucd94\uac00\ub418\uc9c0 \uc54a\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uc774\ub7f0 local \ud0d0\uc0c9 \ube44\uc6a9\uc774 \uc5bc\ub9c8\ub098 \ub192\uc744\uae4c?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\ub178\ub4dc\ub97c contract\ud558\uae30 \uc704\ud55c Local Dijkstra\ud0d0\uc0c9 \ube44\uc6a9\uc774 \ub192\uc744 \uc218 \uc788\ub2e4. \uc608\ub97c \ub4e4\uc5b4 P<sub>max<\/sub>\uac00 \ube44\uad50\uc801 \ud070 \uac12(\uae34 \uac70\ub9ac)\uc774\ub77c\uace0 \ud558\uba74 \ucd5c\ub2e8\uac70\ub9ac P<sub>max&#8217;<\/sub>\ubcf4\ub2e4 \uae34 \uac70\ub9ac\uc758 \ub178\ub4dc\uae4c\uc9c0 \ubc29\ubb38(settle)\ud574\uc57c \ud558\ubbc0\ub85c \ub2e4\uc18c \uc2dc\uac04\uc774 \uc18c\uc694\ub420 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc77c\ubd80\uc5d0\uc11c\ub294 local Dijkstra\ud0d0\uc0c9\uc5d0 heuristic\uc744 \uc801\uc6a9\ud558\ub294 \uacbd\uc6b0\ub3c4 \uc788\ub2e4. \uc608\ub97c \ub4e4\uc5b4, local \ud0d0\uc0c9\uc5d0\uc11c \ubc29\ubb38(settle)\ud558\ub294 \ub178\ub4dc\uc758 \uac1c\uc218\ub97c \uc81c\ud55c\ud558\uae30\ub3c4 \ud55c\ub2e4. \uc885\ub8cc\uc870\uac74\uc778 \ucd5c\ub2e8\uac70\ub9ac\uac00 P<sub>max&#8217;<\/sub>\ubcf4\ub2e4 \uae34 \uac70\ub9ac\uc758 \ub178\ub4dc\uc5d0 \ub3c4\ub2ec\ud558\uae30 \uc804\uc5d0 \uc774 \uc81c\ud55c\uce58(threshold)\uc5d0 \ub3c4\ub2ec\ud558\uac8c \ub418\uba74 \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub807\uac8c \ud558\uba74 \uc2e4\uc9c8\uc801\uc73c\ub85c \ubd88\ud544\uc694\ud55c \uc9c0\ub984\uae38 Edge\uac00 \ucd94\uac00\ub420 \uc218\ub3c4 \uc788\ub2e4. \uc774\ub294 \ucd5c\ub2e8\uac70\ub9ac\uac00 \uc544\ub2d0 \uc218\ub3c4 \uc788\ub294 \uacbd\ub85c&lt;uvw>\uc5d0\uc11c u\uc640 w\uc0ac\uc774\uc758  \uc9c0\ub984\uae38 uw\ub97c \ucd94\uac00\ud574\ubc84\ub9ac\uac8c \ub418\ub294 \uc148\uc774 \ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7fc\uc5d0\ub3c4 \uc9c0\uae08\uae38 Edge\ub294 \ucd5c\ub2e8\uacbd\ub85c \uad6c\uc870\ub97c \uc720\uc9c0\ud558\uae30 \ub54c\ubb38\uc5d0 \uc911\ubcf5\ub41c \uc9c0\ub984\uae38 Edge\ub97c \ucd94\uac00\ud55c\ub2e4\uace0 \ud574\uc11c \uc815\uc0c1\uc801\uc778 \ud0d0\uc0c9\uc744 \ubc29\ud574\ud558\uc9c0\ub294 \uc54a\ub294\ub2e4. \ud558\uc9c0\ub9cc \ucd5c\uc885\uc73c\ub85c \ub9cc\ub4e4\uc5b4\uc9c8 \ub367\ub304(Overlay) \uadf8\ub798\ud504\uc758 \ubc00\ub3c4\uc5d0 \uc601\ud5a5\uc744 \uc8fc\uba70 \ud544\uc694 \uc774\uc0c1\uc73c\ub85c \uc0dd\uc131\ub41c \ub9ce\uc740 \uc9c0\ub984\uae38 Edge\ub4e4\ub85c \uc778\ud574 \ud0d0\uc0c9 \uc2dc\uac04\uc774 \ub290\ub824\uc9c8 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub7f0 local Dijkstra\ud0d0\uc0c9\uc5d0 \ud0d0\uc0c9 \uacf5\uac04\uc758 \ud06c\uae30\ub97c \uc81c\ud55c\ud568\uc73c\ub85c\uc368 \uc804\ucc98\ub9ac\uc5d0 \uc18c\uc694\ub418\ub294 \uc2dc\uac04\uc744 \ud68d\uae30\uc801\uc73c\ub85c \uc904\uc774\uace0 \ubd88\ud544\uc694\ud558\uac8c \ucd94\uac00\ub41c \uc9c0\ub984\uae38 Edge\ub4e4\uc758 \uac2f\uc218\uac00 \ud0d0\uc0c9\uc2dc\uac04\uc5d0 \ub9ce\uc740 \uc601\ud5a5\uc744 \uc8fc\uc9c0 \uc54a\ub294\ub2e4\uba74 \uc815\ud655\ub3c4\uac00 \uc880 \ub5a8\uc5b4\uc9c0\ub294 heuristic\uc744 \uc0ac\uc6a9\ud558\ub294 \uac83\uc740 \ub3c4\uc6c0\uc774 \ub420 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub7f0 Tradeoff\ub294 \uc2e4\uc81c \uad6c\ud604\uacfc\uc815\uc5d0\uc11c \uc801\uc6a9\ud574 \ubcfc\ub9cc\ud558\ub2e4. \uadf8\ub7ec\ub098 \uc704\uc5d0\uc11c \uc124\uba85\ud588\ub358 \uac04\ub2e8\ud55c \ubc29\ubc95\ub3c4 Contraction \ub2e8\uacc4\uc640 Query\ub2e8\uacc4 \ubaa8\ub450\uc5d0\uc11c \ubaa8\ub450 \uc801\uc815\ud55c \uc131\ub2a5\uc744 \ubc1c\ud718\ud588\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7ec\ub098 \uc55e\uc11c \ub9d0\ud588\ub4ef\uc774 \ud544\uc694\uc131\uc774 \uc788\ub294 \uc9c0\ub984\uae38 Edge\ub294 \ube44\ub85d \uacc4\uc18d\ub41c \ucd94\uac00\ub85c \uc778\ud574 \uac70\ucd94\uc7a5\uc2a4\ub7fd\ub354\ub77c\ub3c4 \ud0d0\uc0c9\uc758 \uc815\ud655\ub3c4\uc5d0\ub294 \uc601\ud5a5\uc744 \uc8fc\uc9c0 \uc54a\ub294\ub2e4. \uadf8\ub9ac\uace0 \uc77c\ubc18\uc801\uc778 \ub3c4\ub85c\ub124\ud2b8\uc6cc\ud06c\uc758 \ud3c9\uade0 \ub178\ub4dc \ucc28\uc218(\ub178\ub4dc\uc640 \uc5f0\uacb0\ub41c \ub2e4\ub978 \ub178\ub4dc)\uac00 2.5\uc778 \uc810\uc744 \uac10\uc548\ud558\uba74 local \ud0d0\uc0c9\uc2dc\uac04\uc740 \uc77c\uc815\ud568(constant time)\uc744 \uc608\uc0c1\ud560 \uc218 \uc788\uc73c\uba70 \uc774\ub294 Node\uc758 \uc218\uc640 \ube44\ub840\uc801\uc73c\ub85c(linear time) \uc18c\uc694\uc2dc\uac04\uc774 \uc99d\uac00\ud568\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\ubcc0\ud615\ub41c \uc591\ubc29\ud5a5 \ud0d0\uc0c9(Query)<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\uc81c \uc804\ucc98\ub9ac \ub2e8\uacc4\uc5d0\uc11c \ucc98\ub9ac\ud588\ub358 \uac83\ub4e4\uc5d0 \ub300\ud574 \uace0\ubbfc\ud574 \ubcf4\uc790<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\ubaa8\ub4e0 \ub178\ub4dc\ub97c \uc911\uc694\ub3c4\uc5d0 \ub530\ub77c \uc904\uc138\uc6b0\uae30<\/li>\n\n\n\n<li>\uc904\uc138\uc6b4 \uc21c\uc11c\uc5d0 \ub530\ub77c \uac01 \ub178\ub4dc\ub97c Contract\ud558\uae30<\/li>\n\n\n\n<li>\uae30\uc874 \uadf8\ub798\ud504\uc5d0 \uc788\ub358 Node\uc640 Edge\uc5d0 Contraction\ub2e8\uacc4\uc5d0\uc11c \uc9c0\ub984\uae38 Edge\ub4e4\uc744 \ucd94\uac00\ud55c \ub367\ub304(Overlay) \uadf8\ub798\ud504 G* \uc0dd\uc131<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\uc81c \ucd9c\ubc1c\uc9c0 s\uc640 \ubaa9\uc801\uc9c0 t \uc0ac\uc774\uc5d0 \ucd5c\ub2e8\uac70\ub9ac\ub97c \ucc3e\uae30 \uc704\ud55c \uadf8\ub798\ud504 \ud0d0\uc0c9(Query)\ub97c \uc218\ud589\ud574 \ubcf4\uc790<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">CH\uc758 \ud0d0\uc0c9\uc740 \ubcc0\ud615\ub41c \uc591\ubc29\ud5a5 Dijkstra\ub97c \uc774\uc6a9\ud55c\ub2e4. \uadf8\ub7ec\ub098 \uac01 \ud0d0\uc0c9 \ubc29\ud5a5\ubcc4\ub85c \uadf8\ub798\ud504 G*\uc758 \uaddc\ubaa8\ub97c \ucd95\uc18c\uc2dc\ud0a8 \uc11c\ube0c \uadf8\ub798\ud504\ub97c \ub300\uc0c1\uc73c\ub85c \uc801\uc6a9\ud55c\ub2e4. \uc774\ub97c <strong>upward<\/strong>\uadf8\ub798\ud504\uc640 <strong>downward<\/strong>\uadf8\ub798\ud504\ub85c \ubd80\ub974\uae30\ub85c \ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc55e\uc120 Contraction \uc608\uc81c\uc5d0\uc11c \uc0dd\uc131\ud588\ub358 G*\uadf8\ub798\ud504\ub97c \ubcf5\uae30\ud574 \ubcf4\uba74 \uc801\uc6a9\ud588\ub358 \ub178\ub4dc\uc758 \uc21c\uc11c\ub97c \uc544\ub798 \ub450\ubc88\uca30 \uadf8\ub9bc\uc5d0\uc11c \ud655\uc778\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/contraction\/g-star-graph.png\" alt=\"\" style=\"width:731px;height:auto\"\/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"295\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch20.png\" alt=\"\" class=\"wp-image-1408\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch20.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch20-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch20-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\">\uc0c1\ud5a5(upward) \ud558\ud5a5(downward)  \uadf8\ub798\ud504<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\ub178\ub4dc\uc758 \uc21c\uc11c\ub97c \uace0\ub824\ud574\uc11c \ub178\ub4dc v\uac00 \ub178\ub4dc w\ubcf4\ub2e4 \ub098\uc911\uc5d0 Contract\ub418\uc5c8\ub2e4\uba74 <strong>v > w<\/strong> (v\uc758 \uc6b0\uc120\uc21c\uc704\uac00 w\ubcf4\ub2e4 \ub192\uc74c)\ub85c \ud45c\uc2dc\ud55c\ub2e4. \uadf8\ub9ac\uace0 \ub178\ub4dc w\ubcf4\ub2e4 \uc774\uc804\uc5d0 \ub178\ub4dc v\uac00 Contract\ub418\uc5c8\ub2e4\uba74 <strong>v &lt; w<\/strong>\ub85c \ud45c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7ec\uba74 \uc0c1\ud5a5 \uadf8\ub798\ud504\uc640 \ud558\ud5a5 \uadf8\ub798\ud504\ub97c \uc544\ub798\uc640 \uac19\uc758 \uc815\uc758\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\"><strong>\uc0c1\ud5a5 \uadf8\ub798\ud504(Upward graph)<\/strong> G*<sub>U<\/sub>\ub294 <em>from<\/em> \ub178\ub4dc <em>v<\/em>\uc640 <em>to<\/em> \ub178\ub4dc <em>w<\/em>\ub85c \uc774\ub8e8\uc5b4\uc9c4 Edge(\ub9c1\ud06c)\ub4e4\ub85c\ub9cc \uad6c\uc131\ub41c\ub2e4. \uc774\ub54c v > w \uc870\uac74\uc744 \ub9cc\uc871\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\ud558\ud5a5 \uadf8\ub798\ud504(Downward graph)<\/strong> G*<sub>D<\/sub>\ub294 <em>from<\/em> \ub178\ub4dc <em>v<\/em>\uc640 <em>to<\/em> \ub178\ub4dc <em>w<\/em>\ub97c \uac00\uc9c0\ub294 Edge(\ub9c1\ud06c)\ub4e4\ub85c\ub9cc \uad6c\uc131\ub41c\ub2e4. \uc774\ub54c v &lt; w \uc870\uac74\uc744 \ub9cc\uc871\ud55c\ub2e4.<\/p>\n<\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">\ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uc740 \uac01\uc790 \uace0\uc720\ud55c \uc21c\uc11c\ub97c \uac00\uc9c0\ubbc0\ub85c \ubaa8\ub4e0 Edge\ub294 \uc0c1\ud5a5\uc774\uac70\ub098 \ud558\ud5a5\uc778 \uadf8\ub798\ud504\uc5d0 \ud3ec\ud568\ub41c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uc591\ubc29\ud5a5 \ud0d0\uc0c9\uacf5\uac04(Bidirectionl Search Spaces)<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc624\ub9ac\uc9c0\ub110 \uc591\ubc29\ud5a5 \ud0d0\uc0c9\uc740 \ucd9c\ubc1c\uc9c0\uc5d0\uc11c \uc21c\ubc29\ud5a5 \ud0d0\uc0c9\uc744 \ud558\uace0 \ubaa9\uc801\uc9c0\uc5d0\uc11c \uc5ed\ubc29\ud5a5 \ud0d0\uc0c9\uc744 \uc218\ud589\ud55c\ub2e4. CH\uc5d0\uc11c \ub178\ub4dc s\uc640 t \uc0ac\uc774\uc758 \uacbd\ub85c\ud0d0\uc0c9\uc740 \uadf8\ub798\ud504 G*<sub>U<\/sub>\uc758 \ub178\ub4dc s\uc5d0\uc11c \uc21c\ubc29\ud5a5 \ud0d0\uc0c9\uc744 \ud558\uace0 \uadf8\ub798\ud504 G*<sub>D<\/sub>\uc758 \ub178\ub4dc t\uc5d0\uc11c\ub294 \uc5ed\ubc29\ud5a5 \ud0d0\uc0c9\uc744 \uc9c4\ud589\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7ec\ub098 \ub300\uce6d(symmetric) \uadf8\ub798\ud504\uc77c \uacbd\uc6b0 \uadf8\ub798\ud504 G*<sub>D<\/sub>\uc5d0\uc11c\uc758 \uc5ed\ubc29\ud5a5 \ud0d0\uc0c9(\ub9c1\ud06c\ub97c \ub4a4\uc9d1\uc5b4\uc11c \ud0d0\uc0c9)\uc740 \uadf8\ub798\ud504 G*<sub>U<\/sub>\uc5d0\uc11c \uc21c\ubc29\ud5a5 \ud0d0\uc0c9\uacfc \ub3d9\uc77c\ud558\ub2e4. \ub530\ub77c\uc11c, <span style=\"text-decoration: underline;\">\uadf8\ub798\ud504 G*<sub>U<\/sub>\uc0c1\uc5d0\uc11c \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \ub178\ub4dc\ub85c\ubd80\ud130 \ub3d9\uc2dc\uc5d0 \ucd9c\ubc1c\ud558\ub294 \ud45c\uc900\uc801\uc778 Dijkstra \ud0d0\uc0c9\uc744 \uc218\ud589\ud558\uba74 \ub41c\ub2e4.<\/span><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc55e \uc120 \uc608\uc81c\ub97c \ud65c\uc6a9\ud574\uc11c \ucd9c\ubc1c\uc9c0\ub178\ub4dc\uac00 B\uc774\uace0 \ubaa9\uc801\uc9c0 \ub178\ub4dc\uac00 G\ub77c\uace0 \ud574\ubcf4\uc790. \uadf8\ub7ec\uba74 \uadf8\ub798\ud504 G*<sub>U<\/sub>\uc5d0\uc11c \uc591\ubc29\ud5a5\ubcc4 \ud0d0\uc0c9 \uacf5\uac04\uc740 \uc544\ub798\uc640 \uac19\uc774 \ud615\uc131\ub41c\ub2e4. <\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"736\" height=\"293\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch21.png\" alt=\"\" class=\"wp-image-1429\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch21.png 736w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch21-300x119.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch21-604x240.png 604w\" sizes=\"auto, (max-width: 736px) 100vw, 736px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"295\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch22.png\" alt=\"\" class=\"wp-image-1430\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch22.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch22-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch22-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub798\ud504 G*\uc5d0 \uc18d\ud55c \ubaa8\ub4e0 Edge\ub294 \uadf8\ub798\ud504 G*<sub>U<\/sub> \ub610\ub294 \uadf8\ub798\ud504 G*<sub>D<\/sub>\uc5d0 \uc18d\ud558\uac8c \ub41c\ub2e4\uace0 \ud558\ub354\ub77c\ub3c4 \uadf8\ub798\ud504 G*<sub>U<\/sub>\uc758 \ubaa8\ub4e0 Edge\uac00 \uc8fc\uc5b4\uc9c4 \uc2dc\uc791 Node\uc5d0\uc11c\ubd80\ud130 \ub9cc\ub4e4\uc5b4\uc9c0\ub294 \ud0d0\uc0c9\uacf5\uac04\uc5d0 \ud3ec\ud568\ub418\uc9c0 \uc54a\uc744 \uc218\ub3c4 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc704 \uc608\uc81c\uc5d0\uc11c Edge ED\uc758 \uacbd\uc6b0 E\uac00 D\ubcf4\ub2e4 \uba3c\uc800 Contract\ub418\ubbc0\ub85c \uadf8\ub798\ud504 G*<sub>U<\/sub>\uc5d0 \uc874\uc7ac\ud558\uc9c0\ub9cc \ucd9c\ubc1c\uc9c0 B\uc640 G\uc5d0\uc11c E\uae4c\uc9c0 \uac00\ub294 \uacbd\ub85c\uac00 \uc874\uc7ac\ud558\uc9c0 \uc54a\uc544 Edge ED\ub294 \uace0\ub824\ud560 \ud544\uc694\uac00 \uc5c6\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub4e4 \ub450 \uac1c\uc758 \uc0c1\ud5a5 \uadf8\ub798\ud504\ub97c \ub300\uc0c1\uc73c\ub85c \uc644\uc804\ud55c Dijkstra \ud0d0\uc0c9\uc744 \uc218\ud589\ud55c\ub2e4. \uc774\ub294 \uc591\ubc29\ud5a5 \uc11c\ube0c\uadf8\ub798\ud504\uc0c1\uc758 \ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uc740 \ubc18\ub4dc\uc2dc \ubc29\ubb38(settled)\ub428\uc744 \uc758\ubbf8\ud55c\ub2e4. \uadf8\ub9ac\uace0 \uc591\ubc29\ud5a5 \ud0d0\uc0c9\uc740 \ud2b9\uc131\uc0c1 \ubc29\ubb38\ub41c \ub178\ub4dc\uc758 \uc218\uc640 relax\ub41c Edge\uc758 \uac2f\uc218\ub294 \uadf8\ub798\ud504 G* \uc804\uccb4 \ud0d0\uc0c9(\ud55c \ubc29\ud5a5)\uacfc \ube44\uad50\ud588\uc744 \ub54c \ud6e8\uc52c \uc801\uc744 \uac83\uc774\ub77c\ub294 \uac83\uc740 \uba85\ud655\ud558\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub354\uc6b1\uc774 \ubaa8\ub4e0 \ub178\ub4dc\ub97c \uc644\uc804\ud55c \ud615\ud0dc\ub85c \uc904\uc138\uc6e0\uae30 \ub54c\ubb38\uc5d0 \ub450 \ud0d0\uc0c9\uacf5\uac04\uc740 DAG(Directed Acyclic Graph)\uadf8\ub798\ud504\ub85c \ub098\ud0c0\ub0bc \uc218 \uc788\uc73c\uba70 \ud615\ud0dc\uc0c1(topologically)\uc73c\ub85c\ub294 \uc815\ub82c\ub41c \uc0c1\ud0dc\uac00 \ub41c\ub2e4. \ub450 \ud0d0\uc0c9\uacfc\uc815\uc744 \uadf8\ub9bc\uc73c\ub85c \ud45c\ud604\ud574\ubcf4\uba74 Contraction \uc21c\uc11c\uc758 \uacc4\uce35\uc801 \ud2b9\uc131\uc744 \uba85\ud655\ud788 \uc54c \uc218 \uc788\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/query\/dag-source.png\" alt=\"\" style=\"width:719px;height:auto\"\/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/query\/dag-target.png\" alt=\"\" style=\"width:719px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\">\ucd5c\ub2e8\uacbd\ub85c \uac70\ub9ac \ub3c4\ucd9c<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc5b4\ub5a4 \uacbd\uc6b0\uc5d0\ub77c\ub3c4 \uadf8\ub798\ud504 G*<sub>U<\/sub>\uc758 \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0\uc5d0\uc11c \uc591\ubc29\ud5a5 Dijkstra \ud0d0\uc0c9\uc744 \uc218\ud589\ud558\uba74 \ub450 \ud0d0\uc0c9\uacf5\uac04\uc5d0\uc11c \uacf5\ud1b5\uc73c\ub85c \ubc29\ubb38\ub41c \ub178\ub4dc\ub4e4\uc774 \uc874\uc7ac\ud558\uba70 \uc774\ub4e4 \ub178\ub4dc \uc9d1\ud569\uc744 L\ub85c \ud45c\ud604\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc704\uc758 \uc608\uc81c\ub97c \uac00\uc9c0\uace0 \uc598\uae30\ub97c \uc774\uc5b4\uac00\uc790\uba74 \uc9d1\ud569 L\uc758 \ub178\ub4dc \uc911 \ucd5c\ub2e8\uac70\ub9ac\ub97c \ube68\uac04\uc0c9\uc73c\ub85c \uce60\ud55c \ub178\ub4dc\ub4e4\uc744 \ubcfc \uc218 \uc788\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/query\/query-scores.png\" alt=\"\" style=\"width:723px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc9d1\ud569 L\uc5d0 \uc18d\ud55c \ubaa8\ub4dc \ub178\ub4dc v\uc5d0 \ub300\ud574 \ub178\ub4dc v\uae4c\uc9c0\uc758 \ucd5c\ub2e8\uac70\ub9ac\ub97c \ud569\uc0b0\ud588\ub2e4(s\ub85c\ubd80\ud130\uc758 \uac70\ub9ac\uc640 t\ub85c\ubd80\ud130\uc758 \uac70\ub9ac). \ucd5c\ub2e8\uacbd\ub85c\uc758 \uac70\ub9ac\ub294 \uc9d1\ud569 L\uc5d0 \uc18d\ud55c \ubaa8\ub4e0 \ub178\ub4dc v\uc5d0\uc11c \uac70\ub9ac\ud569(\uc815\ubc29\ud5a5\/\uc5ed\ubc29\ud5a5)\uc774 \ucd5c\uc18c\uc778 \uac12\uc774 \ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub2e4\uc2dc \ub9d0\ud558\uba74 \uc544\ub798\uc640 \uac19\uc774 \ud45c\ud604\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\">dist(s, t) = min{ dist(s, v) + dist(v, t) } over v in L<\/p>\n<\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">\ub530\ub77c\uc11c, \uc704 \uadf8\ub9bc\uc744 \ubcf4\uba74 \ucd9c\ubc1c\uc9c0 \ub178\ub4dc B\uc640 \ubaa9\uc801\uc9c0 \ub178\ub4dc G\uc5d0 \ub300\ud574 3\uac1c\uc758 \ub178\ub4dc \uc989, H, F, A\uac00 \ubc29\ubb38(settled)\ub418\uc5c8\ub2e4. \uadf8\ub9ac\uace0 \ub178\ub4dc H\uac00 <em>dist(B, H) + dist(G, H) = 10<\/em> \uc774 \ub418\ubbc0\ub85c \uc774\ub4e4 3\uac1c\uc758 Node \uc911\uc5d0 \ucd5c\uc18c\uac12\uc744 \uac00\uc9c4\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub294 B\uc640 G\uc0ac\uc774\uc5d0 \ucd5c\ub2e8\uacbd\ub85c\uc758 \uac70\ub9ac\ub294 10\uc774 \ub418\uace0 H\ub97c \ud1b5\uacfc\ud568\uc744 \uc758\ubbf8\ud55c\ub2e4. \uc544\ub798 G*\uadf8\ub798\ud504\uc5d0\uc11c \uc774\ub97c \ud655\uc778\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/query\/query-path.png\" alt=\"\" style=\"width:722px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc591\ubc29\ud5a5 Dijkstra \ud0d0\uc0c9\uc740 \uc815\ud655\ud55c \uacbd\ub85c\ub97c \uc0b0\ucd9c\ud558\uba70 \ud0d0\uc0c9\ud558\ub294 \ub3d9\uc548 16\uac1c\uc758 Edge(\ub9c1\ud06c)\ub9cc relax\ud55c \uc148\uc774 \ub41c\ub2e4. \uc774\ub294 \uc6d0\ub798 \uadf8\ub798\ud504\uc77c \uacbd\uc6b0 40\uac1c\uc758 Edge\ub97c relax\ud574\ub2e4 \ud558\ub294 \uac83\uacfc \ube44\uad50\ud558\uba74 \ub9ce\uc774 \uc904\uc5b4\ub4e0 \uac83\uc784\uc744 \ud655\uc778\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc704\uc758 \uc608\uc640 \uac19\uc774 \uaddc\ubaa8\uac00 \uc791\uc740 \uadf8\ub798\ud504\ub97c \ub300\uc0c1\uc73c\ub85c \ud560 \uacbd\uc6b0 \uc18d\ub3c4\ud5a5\uc0c1\uc774 \ub208\uc5d0 \ub744\uc9c0 \uc54a\uc9c0\ub9cc \uc2e4\uc81c \ub3c4\ub85c\ub124\ud2b8\uc6cc\ud06c\uc5d0 \uc801\uc6a9\ud558\uba74 \ud0d0\uc0c9\uacf5\uac04\uc744 \uc5c4\uccad\ub098\uac8c \uc904\uc77c \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uc9c0\ub984\uae38 \uacbd\ub85c \ubcf5\uc6d0<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\ucd5c\ub2e8\uacbd\ub85c\uc758 \uac70\ub9ac\ub97c \ub3c4\ucd9c\ud560\uc218 \uc788\uc9c0\ub9cc \uc5ec\uae30\uc5d0 \ub354\ud574 \uc9c0\ub984\uae38 \uacbd\ub85c\uc5d0 \ud3ec\ud568\ub41c \uc2e4\uc81c \ub9c1\ud06c\ub4e4\ub3c4 \ubcf5\uc6d0\uc2dc\ucf1c\uc57c \ud55c\ub2e4. Contraction\uacfc\uc815\uc5d0\uc11c \uc9c0\ub984\uae38 Edge\ub97c \ucd94\uac00\ud560 \ub54c \uc774 \uacfc\uc815\uc744 \ucc98\ub9ac\ud560 \uc218 \uc788\ub2e4. Node v\ub97c Contraction\ud558\ub294 \uacfc\uc815\uc5d0\uc11c Node u\uc5d0\uc11c w\ub85c \uac00\ub294 \uc9c0\ub984\uae38 Edge\ub97c \ucd94\uac00\ud560 \ub54c v\ub97c \uac00\ub9ac\ud0a4\ub294 \uc9c0\ub984\uae38 Pointer\ub3c4 \uac19\uc774 \uc800\uc7a5\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc591 \ubc29\ud5a5\uc758 \uadf8\ub798\ud504 G*<sub>U<\/sub>\uc5d0\uc11c \ucd5c\ub2e8\uacbd\ub85c\ub97c \ubcf5\uc6d0\ud560 \ub54c \uc911\uc694\ub3c4\uac00 \uac00\uc7a5 \ub192\uc740 Node\ubd80\ud130 \uc2dc\uc791\ud55c\ub2e4. \uc77c\ubc18 Dijkstra Algorithm\uc5d0\uc11c \uc774\uc804 \ub9c1\ud06c\ub97c \ucc3e\uc544\uac00\ub294 \ubc29\uc2dd\ucc98\ub7fc \ubd80\ubaa8 Edge\ub97c \uc5ed\uc73c\ub85c \ucd94\uc801\ud574 \ub098\uac00\uba74 \ub41c\ub2e4. \ubd80\ubaa8 Edge\uac00 \uc9c0\ub984\uae38 Pointer\ub97c \ud3ec\ud568\ud558\uace0 \uc788\ub2e4\uba74 \ubd80\ubaa8 Edge\ub97c \uc9c0\ub984\uae38 Edge\ub85c \uce58\ud658\ud558\uba70 \uc804\uccb4 \uacbd\ub85c\ub97c \ubcf5\uc6d0\ud560 \ub54c\uae4c\uc9c0 \uc7ac\uadc0\uc801\uc73c\ub85c \uc774 \uacfc\uc815\uc744 \uc218\ud589\ud574 \ub098\uac04\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc704\uc758 \ud0d0\uc0c9 \uc608\uc81c\uc5d0\uc11c\ub294 \uc9c0\ub984\uae38 \uacbd\ub85c\uac00 \ud3ec\ud568\ub41c \ud615\ud0dc\ub85c \ub9cc\ub4e4\uc5b4\uc9c0\uc9c0 \uc54a\uc558\ub2e4. \ud558\uc9c0\ub9cc \ub178\ub4dc A\uc5d0\uc11c G\ub85c \uac00\ub294 \ucd5c\ub2e8\uacbd\ub85c\ub97c \ud0d0\uc0c9\ud55c\ub2e4\uace0 \uc0dd\uac01\ud574\ubcf4\uba74 \uc9c0\ub984\uae38 \uacbd\ub85c AH\uac00 \ubc18\ub4dc\uc2dc \ud3ec\ud568\ub420 \uac83\uc774\ub2e4. \uc5ec\uae30\uc11c Contraction\uc774 \uc774\ub8e8\uc5b4\uc9c4 \uc21c\uc11c\uc0c1\uc73c\ub85c \ubcf4\uba74 \ub178\ub4dc A\uc758 \uc6b0\uc120\uc21c\uc704\uac00 \uac00\uc7a5 \ub192\uae30 \ub584\ubb38\uc5d0 \uc9c0\ub984\uae38 \uacbd\ub85c\uc758 \ubcf5\uc6d0\uacfc\uc815\uc744 \uc544\ub798\uc640 \uac19\uc774 \uc2dc\uac01\ud654 \ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/query\/shortcut-unpack.png\" alt=\"\" style=\"width:699px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\">\ud0d0\uc0c9 \uac80\uc99d(Query Correctness)<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\uc784\uc758\uc758 Contraction\uc21c\uc11c\ub85c \ub9cc\ub4e4\uc5b4\uc9c4 \uadf8\ub798\ud504 G*\uc0c1\uc5d0\uc11c \uc55e\uc5d0\uc11c \uc124\uba85\ud588\ub358 \ud0d0\uc0c9(Query) Algorithm\uc774 \uc815\ud655\ud558\uac8c \ub3d9\uc791\ud558\ub294\uc9c0\ub97c \uc124\uba85\ud558\ub824\uace0 \ud55c\ub2e4. \ub098\uc544\uac00 \uadf8\ub798\ud504 G*\uc5d0\uc11c\uc758 \ucd5c\ub2e8\uacbd\ub85c\uac00 \uc6d0\ubcf8 \uadf8\ub798\ud504\uc778 G\uc5d0\uc11c\ub3c4 \ucd5c\ub2e8\uacbd\ub85c\uac00 \ub418\ub294\uc9c0\ub3c4 \uac19\uc774 \uc0b4\ud3b4\ubcf4\ub3c4\ub85d \ud55c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\ud45c\uae30\ubc95 \uc124\uba85<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc55e\uc5d0\uc11c \uc124\uba85\ud560 \ub54c \ud65c\uc6a9\ud558\uae34 \ud588\uc9c0\ub9cc \ub2e4\uc2dc \ubcf5\uae30\ud558\uc790\uba74<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uc9d1\ud569 V\uc5d0 \uc18d\ud55c \ubaa8\ub4e0 \ub178\ub4dc v \uc5d0 \ub300\ud574 \ub178\ub4dc \uc21c\uc11c\ub294 O = {v<sub>1<\/sub>, &#8230;, v<sub>n<\/sub>} \ub85c \ud45c\uae30<\/li>\n\n\n\n<li>\uc6d0\ubcf8 \uadf8\ub798\ud504 G\ub97c G<sub>0<\/sub>\ub85c \ud45c\uae30\ud558\uace0 \uadf8\ub798\ud504 G<sub>i-1<\/sub>\uc758 \ub178\ub4dc v<sub>i<\/sub>\ub97c Contraction\ud568\uc73c\ub85c\uc368 \uc0dd\uc131\ub41c \uc11c\ube0c \uadf8\ub798\ud504\ub97c G<sub>i<\/sub>\ub77c\uace0 \ud45c\uae30<\/li>\n\n\n\n<li>\uc774\uc81c <em>G<sub>i<\/sub><\/em>\ub294 v<sub>i<\/sub> , \uadf8\ub9ac\uace0 v<sub>i<\/sub>\uc640 \uc778\uc811\ud55c Edge\ub4e4\uc774 \uc81c\uc678\ub41c \uc0c1\ud0dc\uc784. \uadf8\ub7ec\ub098 v<sub>i<\/sub>\uac00 Contract\ub418\uba74\uc11c \uc0c8\ub85c \ucd94\uac00\ub41c \uc9c0\ub984\uae38 Edge\ub4e4\uc740 \ud3ec\ud568\ud558\uace0 \uc788\uc74c. \ub530\ub77c\uc11c <em>G<sub>i<\/sub><\/em>\ub294 <em>n-i<\/em> \uac1c\uc758 \ub178\ub4dc\ub85c \uad6c\uc131\ub428.<\/li>\n\n\n\n<li>\uadf8\ub798\ud504 G<sub>i<\/sub>\uc0c1\uc758 \ub450 \ub178\ub4dc u, v \uc0ac\uc774\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub294 <em>dist<sub>i<\/sub>(u, v)<\/em>\ub85c \ud45c\uae30 \ud568<\/li>\n\n\n\n<li>\ub367\ub304(Overlay) \uadf8\ub798\ud504 G*\ub294 \uadf8\ub798\ud504 G\uc758 \ubaa8\ub4e0 \ub178\ub4dc\uc640 Edge\uc5d0 \ub354\ud574 \uadf8\ub798\ud504 {<em>G<sub>1<\/sub>, &#8230; G<sub>n-1<\/sub><\/em>}\uc5d0\uc11c \ucd94\uac00\ub41c \ubaa8\ub4e0 \uc9c0\ub984\uae38 Edge\ub4e4\ub3c4 \ud3ec\ud568\ud558\uace0 \uc788\uc74c<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">\ubcf4\uc870\uba85\uc81c 1: \ubaa8\ub4e0 \ub178\ub4dc\ub97c \ub300\uc0c1\uc73c\ub85c Contraction\ud558\ub354\ub77c\ub3c4 \ucd5c\ub2e8\uacbd\ub85c\ub294 \uc720\uc9c0\ub41c\ub2e4.<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub294 \ub450 \ub178\ub4dc\uc0c1\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub294 Contraction \uc804\uacfc \ud6c4\uac00 \ub3d9\uc77c\ud558\ub2e4\ub294 \uac83\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ud45c\ud604\ud558\uc790\uba74:<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\">\uadf8\ub798\ud504 G<sub>i<\/sub>\uc758 \ubaa8\ub4e0 \ub178\ub4dc s\uc640 t\uc5d0 \ub300\ud574 dist<sub>i<\/sub>(s, t) = dist<sub>i-1<\/sub>(s, t)\uc744 \ub9cc\uc871\ud55c\ub2e4. \uc774\ub54c i \ub294 [1, n] \uc0ac\uc774\uc758 \uac12\uc744 \ub098\ud0c0\ub0c4<\/p>\n<\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub798\ud504 G<sub>i<\/sub>\uc758 \ub178\ub4dc s\uc5d0\uc11c t\uae4c\uc9c0\uc758 \ucd5c\ub2e8\uacbd\ub85c P\uac00 \uc788\ub2e4\uba74 v<sub>i<\/sub>\uac00 Contraction \ub41c \ud6c4 P\ub294 \uc9c0\ub984\uae38 Edge\ub97c \ud3ec\ud568\ud560 \uc218\ub3c4 \uc788\uace0 \uadf8\ub807\uc9c0 \uc54a\uc744 \uc218\ub3c4 \uc788\ub2e4. \ub9cc\uc57d \uc9c0\ub984\uae38 Edge\uac00 \ud3ec\ud568\ub418\uc9c0 \uc54a\ub294\ub2e4\uba74 P\ub294 \uadf8\ub798\ud504 G<sub>i-1<\/sub>\uc5d0\ub3c4 \ubc18\ub4dc\uc2dc \uc874\uc7ac\ud55c\ub2e4.  \ub9cc\uc57d Contraction\uacfc\uc815\uc5d0\uc11c P\uac00 \uc9c0\ub984\uae38 Edge\ub97c \ud3ec\ud568\ud560 \uacbd\uc6b0 u\uc640 w\uac00 v<sub>i<\/sub>\uc758 \uc774\uc6c3\ub178\ub4dc\uc774\uace0 \uc9c0\ub984\uae38 Edge\ub97c uw\ub77c\uace0 \uac00\uc815\ud574\ubcf4\uc790. \uadf8\ub7ec\uba74 \uadf8\ub798\ud504 G<sub>i-1<\/sub>\uc5d0\uc11c\ub294 \uacbd\ub85c \uc911 cost\uac00 uw\uc640 \ub3d9\uc77c\ud55c \uacbd\ub85c &lt;uv<sub>i<\/sub>w> \uac00 \uc874\uc7ac\ud560 \uac83\uc774\ub2e4. \uc65c\ub0d0\ud558\uba74 v<sub>i<\/sub>\ub97c contraction\ud55c \ud6c4 \uc9c0\ub984\uae38(uw)\uc744 \ucd94\uac00\ud588\uae30 \ub54c\ubb38\uc5d0 \ub2f9\uc5f0\ud55c \uc598\uae30\uac00 \ub41c\ub2e4. \ub530\ub77c\uc11c dist<sub>i-1<\/sub>(s, t) &lt;= dist<sub>i<\/sub>(s, t)\uac00 \ub41c\ub2e4.(???, = \uc77c \uac83\uc73c\ub85c \ucd94\uc815)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ube44\uc2b7\ud55c \ubc29\ubc95\uc73c\ub85c \uc774\uc81c \uadf8\ub798\ud504 G<sub>i-1<\/sub>\uc5d0\uc11c \ub178\ub4dc s\ubd80\ud130 t\uae4c\uc9c0\uc758 \ucd5c\ub2e8\uacbd\ub85c\uac00 \uc788\ub2e4\uace0 \uc0dd\uac01\ud574\ubcf4\uc790. P\uac00 v<sub>i<\/sub>(\ub2e4\uc74c round\uc5d0\uc11c Contraction\ub420 \ub178\ub4dc)\ub97c \ud1b5\uacfc\ud558\ub294 Edge\ub97c \uac00\uc9c8 \uc218\ub3c4 \uc788\uace0 \uc544\ub2d0 \uc218\ub3c4 \uc788\ub2e4. \ub9cc\uc57d v<sub>i<\/sub>\ub97c \ud1b5\uacfc\ud558\uc9c0 \uc54a\ub294\ub2e4\uba74 \ucd5c\ub2e8\uacbd\ub85c P\ub294 G<sub>i<\/sub>\uc5d0\uc11c \uc874\uc7ac\ud558\ub294 \uac83\uacfc \uac19\uc774 \uadf8\ub798\ud504 G<sub>i-1<\/sub>\uc5d0\uc11c\ub3c4 \ub3d9\uc77c\ud558\uac8c \uc874\uc7ac\ud558\uace0 \uc788\uc744 \uac83\uc774\ub2e4. \ub9cc\uc57d P\uac00 v<sub>i<\/sub>\ub97c \ud1b5\uacfc\ud558\ub294 Edge\ub97c \ud3ec\ud568\ud55c\ub2e4\uba74 \uadf8\ub798\ud504 G<sub>i<\/sub>\uc5d0\uc11c\ub294 \ub3d9\uc77c\ud55c weight(cost)\ub97c \uac16\ub294 \uc9c0\ub984\uae38 Edge\uac00 \ucd94\uac00\ub420 \uac83\uc774\ub2e4. \ub530\ub77c\uc11c dist<sub>i<\/sub>(s, t) &lt;= dist<sub>I-1<\/sub>(s, t)\uac00 \uc131\ub9bd\ud55c\ub2e4. (???, = \uc77c \uac83\uc73c\ub85c \ucd94\uc815)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub530\ub77c\uc11c, <strong>dist<sub>i<\/sub>(s, t) = dist<sub>i-1<\/sub>(s, t)<\/strong>\uac00 \uc131\ub9bd\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774 \uacb0\uacfc\ub294 \ub300\uccb4\ub85c \uba85\ub8cc\ud558\uc9c0\ub9cc \uc2dc\uac01\uc801\uc778 \uc608\uc81c\uac00 \ud544\uc694\ud558\ub2e4\uba74 \ucd08\uae30 contraction \uc608\uc81c\ub97c \uc0dd\uac01\ud574\ubcf4\uba74 \ub41c\ub2e4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"734\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch23.png\" alt=\"\" class=\"wp-image-1442\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch23.png 734w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch23-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch23-604x242.png 604w\" sizes=\"auto, (max-width: 734px) 100vw, 734px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"295\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch24.png\" alt=\"\" class=\"wp-image-1443\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch24.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch24-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch24-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"736\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch25.png\" alt=\"\" class=\"wp-image-1444\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch25.png 736w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch25-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch25-604x241.png 604w\" sizes=\"auto, (max-width: 736px) 100vw, 736px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\">\ud0d0\uc0c9(Query)\ub294 \uc815\ud655\ud558\ub2e4(Query is Correct)<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc544\ub798\uc758 \uc2dd\uc744 \uc99d\uba85\ud558\uae30 \uc704\ud574 \uba85\uc81c 1\uc744 \ud65c\uc6a9\ud55c\ub2e4.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\"><em><strong>dist(s, t)<\/strong> = min{ dist(s, v) + dist(v, t) } over all v in L<\/em><\/p>\n<\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">\uc5ec\uae30\uc11c L\uc744 \uadf8\ub798\ud504 G*<sub>U<\/sub>\uc758 Node s\uc640 t\uc5d0\uc11c \uc2dc\uc791\ud558\ub294 \uc591\ubc29\ud5a5 \ud0d0\uc0c9\uc5d0\uc11c \ubaa8\ub450 \ubc29\ubb38\ud55c(settled) \ub178\ub4dc \uc9d1\ud569\uc774\ub77c\uace0 \ud558\uc790. \uc774\uc81c \uadf8\ub798\ud504 G\uc5d0\uc11c \ub178\ub4dc s\ubd80\ud130 t\uae4c\uc9c0 \ucd5c\ub2e8\uacbd\ub85c\ub97c \uc0dd\uac01\ud574\ubcf4\uc790. \uc5ec\uae30\uc11c \uacbd\ub85c P\uc0c1\uc5d0 \uc788\ub294 \ub178\ub4dc \uc911 \uc6b0\uc120\uc21c\uc704\uac00 \uac00\uc7a5 \ub192\uc740 \ub178\ub4dc(\ub9e8 \ub098\uc911\uc5d0 contract\ub41c \ub178\ub4dc)\ub97c <strong>vertex m<\/strong> \uc774\ub77c \uc815\uc758\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ucd94\ud6c4\uc5d0 \ubcf4\uac15 \uc608\uc815&#8230;<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\ub178\ub4dc \uc21c\uc11c \uc120\uc815<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\ub178\ub4dc\uac00 contract\ub418\ub294 \uc21c\uc11c\uc640 \uc0c1\uad00\uc5c6\uc774 \ud0d0\uc0c9\uc740 \uc815\uc0c1\uc801\uc73c\ub85c \ub3d9\uc791\ud55c\ub2e4. \uadf8\ub7ec\ub098 \ub178\ub4dc \uc904\uc138\uc6b0\uae30\ub97c \uc5b4\ub5bb\uac8c \ud558\ub290\ub0d0\uc5d0 \ub530\ub77c \ud0d0\uc0c9 \uc131\ub2a5\uc5d0\ub294 \ub9ce\uc740 \uc601\ud5a5\uc744 \uc904 \uc218 \uc788\ub2e4. \uc9c0\ub984\uae38 Edge\uac00 \uadf8\ub798\ud504 G*\uc5d0 \ucd94\uac00\ub420\uc9c0 \uc5ec\ubd80\ub294 \ub178\ub4dc\uac00 Contraction\ub418\ub294 \uc21c\uc11c\uc5d0 \uc601\ud5a5\uc744 \ubc1b\ub294\ub2e4. \uc55e\uc11c \uc5b8\uae09\ub418\uae34 \ud588\uc9c0\ub9cc \uc9c0\ub984\uae38 Edge\uac00 \ub108\ubb34 \ub9ce\uc544\uc9c0\uba74 \uadf8\ub798\ud504 G*\uc758 \ubc00\uc9d1\ub3c4\uac00 \ub192\uc544\uc9c0\uace0 \uc774\ub85c \uc778\uc5d0 \ud0d0\uc0c9 \uc131\ub2a5\uc774 \ub5a8\uc5b4\uc9c0\ub294 \uacb0\uacfc\ub97c \ucd08\ub798\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub530\ub77c\uc11c CH\uc5d0\uc11c\uc758 \ucd5c\ub300 \uad00\uc2ec\uc0ac\ub294 \uc804\ucc98\ub9ac(Preprocessing) \ub2e8\uacc4\uc5d0\uc11c \uc5b4\ub5bb\uac8c \ub178\ub4dc\ub97c \uc904\uc138\uc6b8 \uac83\uc778\uac00\uac00 \ub41c\ub2e4. \uc774\uc0c1\uc801\uc778 \ub178\ub4dc \uc904\uc138\uc6b0\uae30\ub294 \uc27d\uc9c0 \uc54a\uc740 \uac83\uc73c\ub85c \uc54c\ub824\uc838 \uc788\ub2e4. CH\uc640 \uad00\ub828\ub41c \ub9ce\uc740 \uc5f0\uad6c\uc640 \uac1c\ubc1c \uacfc\uc815\uc5d0\uc11c \uc5b4\ub5bb\uac8c \ud558\uba74 \ub178\ub4dc \uc904\uc138\uc6b0\uae30 \ub97c \uc798 \ud560 \uc218 \uc788\uc744\uc9c0\ub97c \ub2e4\ub8e8\uace0 \uc788\ub2e4. \uadf8 \uc911 \uc544\ub798\uc640 \uac19\uc740 \ubc29\ubc95\uc740 \uc2e4\uc81c \uc801\uc6a9\ud588\uc744 \ub54c \ub192\uc740 \uc131\ub2a5\uc744 \ubcf4\uc5ec \uc900\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\ub178\ub4dc \uc904\uc138\uc6b0\uae30 \uc804\ub7b5<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc77c\ubc18\uc801\uc73c\ub85c \uc0dd\uac01\ud574 \ubcfc \uc218 \uc788\ub294 \ubc29\ubc95\uc740 \ubaa8\ub4e0 \ub178\ub4dc\ub9c8\ub2e4 Contract \uc218\ud589\uacfc \uad00\ub828\ub41c \uc77c\uc885\uc758 Cost\ub97c \ubd80\uc5ec\ud558\uace0 Cost\uac00 \uac00\uc7a5 \uc801\uc740 \uac83\ubd80\ud130 \uac00\uc7a5 \ub192\uc740 \uac83\uae4c\uc9c0 \uc904\uc744 \uc138\uc6b0\ub294 \uac83\uc774\ub2e4. \ucd08\uae30\uc5d0 \uc598\uae30\ud588\ub358 \uac83\ucc98\ub7fc Cost\ub97c \uc911\uc694\ub3c4\ub97c \ub098\ud0c0\ub0b4\ub294 \ucc99\ub3c4\ub85c \uc0dd\uac01\ud574 \ubcfc \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774 Cost\ub97c \uc0b0\uc815\ud558\uae30 \ud560 \ub54c \uc8fc\ub85c \uc801\uc6a9\ud558\ub294 \uae30\ub2a5\uc73c\ub85c \uac01 \ub178\ub4dc\ub97c \ub300\uc0c1\uc73c\ub85c Contraction\uc744 \uc2dc\ubbac\ub808\uc774\uc158 \ud574\ubcf4\ub294 \ubc29\ubc95\uc774 \uc788\ub2e4. Contraction\uacfc\uc815\uc5d0\uc11c \ud2b9\uc815 \ub178\ub4dc\uc640 \uc778\uc811\ud55c \ubaa8\ub4e0 Edge\ub4e4\uc744 \uc81c\uac70\ud55c\ub2e4\uace0 \ud588\uc744 \ub54c \ub178\ub4dc\uc5d0 \uc5f0\uacb0\ub41c Edge\ub4e4\uc758 \uac2f\uc218 \ucc28\uc774\ub97c \ud65c\uc6a9\ud55c\ub2e4. \uc989 \ucd08\uae30\uc758 Edge \uc0c1\ud0dc\uc5d0\uc11c \uc81c\uac70\ub41c Edge \uac1c\uc218\uc640 \uc0c8\ub85c \ucd94\uac00\ub41c \uc9c0\ub984\uae38 Edge \uac2f\uc218\uc758 \ucc28\uc774\ub97c \uc774\uc6a9\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc55e\uc5d0\uc11c \ubd24\ub358 \uadf8\ub798\ud504\ub97c \ub2e4\uc2dc \uac00\uc838\uc624\uba74<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/img\/contraction\/contract-full-1.png\" alt=\"\" style=\"width:590px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\ucc98\uc74c\uc5d0 \uc784\uc758\ub85c \uc815\uc758\ud55c \ub178\ub4dc \uc21c\uc11c\ub97c \uc774\uc6a9\ud560 \uacbd\uc6b0 \ub2e8\uc9c0 3\uac1c\uc758 \uc9c0\ub984\uae38 Edge\ub9cc\uc774 \ucd5c\uc885 \ucd94\uac00\ub418\uc5c8\ub2e4. \ucd5c\ucd08\ub85c \ub178\ub4dc B\uac00 Contract\ub418\uc5c8\uc9c0\ub9cc \uc774 \uacfc\uc815\uc5d0\uc11c\ub294 \uc9c0\ub984\uae38 Edge\ub294 \ucd94\uac00\ub418\uc9c0 \uc54a\uc558\ub2e4. \ub2e4\uc2dc\ub9d0\ud574 \ub178\ub4dc B\uc758 Edge Difference\ub294 -3\uc774 \ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7ec\ub098 \ub178\ub4dc J\ub97c \uba3c\uc800 Contract \ud55c\ub2e4\uba74 \uc5b4\ub5bb\uac8c \ub420\uae4c? B\ub300\uc2e0 \ub178\ub4dc J\ub97c \uc120\ud0dd\ud558\uba74 \uc5b4\ub5bb\uac8c \ub418\ub294\uc9c0 \ube44\uad50\ud574 \ubcf4\uc790.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch26.png\" alt=\"\" class=\"wp-image-1454\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch26.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch26-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch26-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"733\" height=\"293\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch27.png\" alt=\"\" class=\"wp-image-1455\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch27.png 733w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch27-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch27-604x241.png 604w\" sizes=\"auto, (max-width: 733px) 100vw, 733px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch28.png\" alt=\"\" class=\"wp-image-1456\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch28.png 735w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch28-300x120.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/ch28-604x242.png 604w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\ub178\ub4dc J\ub294 B\ubcf4\ub2e4 \ud6e8\uc52c \ud070 Edge Difference\ub97c \ubcf4\uc5ec\uc900\ub2e4. \ub530\ub77c\uc11c \ucd08\ubc18\ubd80\uc5d0 J\ub97c contract\ud55c\ub2e4\ub294 \uac83\uc740 \uc88b\uc544\ubcf4\uc774\uc9c0 \uc54a\ub294\ub2e4. \ub178\ub4dc J\uc758 \uacbd\uc6b0\ub294 \uc774\uc6c3 \ub178\ub4dc\ub4e4\uacfc \ub0ae\uc740 Cost\uc758 Edge\ub85c \uc5f0\uacb0\ub418\ub294 \uc911\uc2ec\ubd80\uc5d0 \uc788\ub2e4. \uc774\ub54c \uc778\uc811\ud558\ub294 Edge\ub4e4\uc740 \ub178\ub4dc B\uc640 G\uc0ac\uc774\uc758 \ucd5c\ub2e8\uacbd\ub85c\uc5d0\uc11c \ucc98\ub7fc \uba3c\uac70\ub9ac\ub97c \uc5ec\ud589\ud560 \ub54c \uacbd\ub85c \uc911\ubc18\ubd80\uc5d0 \uc8fc\ub85c \uc774\uc6a9\ud558\ub294 \uace0\uc18d\ub3c4\ub85c\uc640 \uac19\uc740 \ub3c4\ub85c\uc5d0 \ud574\ub2f9\ud55c\ub2e4. \ub530\ub77c\uc11c J\uc640 \uac19\uc740 \ub178\ub4dc\ub294 \uc911\uc694\ub3c4\uac00 \ub192\uc740 \ub178\ub4dc\uc774\uba70 \ucd5c\uace0\uc758 \ud0d0\uc0c9\uc131\ub2a5\uc744 \uae30\ub300\ud55c\ub2e4\uba74 \ucd08\uae30\uc5d0 contract \ud574\uc11c\ub294 \uc548\ub41c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uc21c\uc11c\uacc4\uc0b0\uacfc Node Contraction<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\ub178\ub4dc\uc21c\uc11c\ub97c \uacb0\uc815\ud558\uace0 \uc774 \uc815\ud574\uc9c4 \uc21c\uc11c\ub300\ub85c Contraction\uc744 \uc218\ud589\ud558\ub294 \ucd08\uae30 \ubc29\ubc95\uc73c\ub85c Cost Function\uc5d0 \uae30\ubc18\ud558\uc5ec \uc77c\uc885\uc758 Priority Queue\ub97c \uc801\uc6a9\ud574 \ubcfc \uc218 \uc788\ub2e4. \uc774 \uacbd\uc6b0 Priority\ub294 \uac01 \ub178\ub4dc\ubcc4 Edge Difference\uac00 \ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub530\ub77c\uc11c, \uba3c\uc800 Priority Queue\ub97c \ub85c\ub529\ud558\ub824\uba74 \uac01 \ub178\ub4dc\uac00 Contraction\ub420 \ub54c\ub97c \uc2dc\ubbac\ub808\uc774\uc158\ud574\uc11c Edge Difference\ub97c \uacc4\uc0b0\ud55c\ub2e4. \uc55e\uc5d0\uc11c \ub2e4\ub918\ub358 \uc9c0\ub984\uae38 Edge \uacc4\uc0b0 \ubc29\ubc95\uc744 \ud65c\uc6a9\ud574\uc11c \uac01 \ub178\ub4dc\ub9c8\ub2e4 \uc77c\ub828 \uacc4\uc0b0 \uc791\uc5c5\uc744 \uc218\ud589\ud55c\ub2e4. \uc774 \ub2e8\uacc4\uc758 \uc791\uc5c5\uc740 \ub178\ub4dc \uac1c\uc218\uc5d0 \ube44\ub840\ud55c \uc791\uc5c5\uc2dc\uac04\uc774 \uc18c\uc694\ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7ec\ub098 \ub178\ub4dc Contraction\uc791\uc5c5 \uc2dc\uc791 \uc774\ud6c4\uc5d0\ub294 \ub2e4\ub978 \ub178\ub4dc\ub4e4\uc758 Edge Difference\uc5d0\ub3c4 \uc601\ud5a5\uc744 \uc904 \uc218 \uc788\ub2e4\ub294 \uc810\uc744 \uace0\ub824\ud574\uc57c \ud55c\ub2e4. \ub9cc\uc57d Edge\uac1c\uc218 \ucc28\uc774\ub97c \uae30\uc900\uc73c\ub85c \ub178\ub4dc \uc904\uc138\uc6b0\uae30\ub97c \uc5c4\uaca9\ud558\uac8c \uc801\uc6a9\ud560 \uacbd\uc6b0 Contraction \uc218\ud589 \ud6c4\uc5d0 \uadf8\ub798\ud504\uc5d0 \ub0a8\uc544 \uc788\ub294 \ubaa8\ub4e0 \ub178\ub4dc\ub97c \ub300\uc0c1\uc73c\ub85c Edge Difference \uc7ac\uacc4\uc0b0 \ud574\uc57c \ud560 \uc218 \uc788\ub2e4. \ubb3c\ub860 \uc774\ub807\uac8c \ud558\uba74 \uc5c4\uccad\ub09c \uc2dc\uac04\uc774 \uc18c\uc694\ub420 \uac83\uc774\uba70 \ud604\uc2e4\uc801\uc73c\ub85c \uc218\ud589\uc774 \ubd88\uac00\ub2a5\ud558\ub2e4. \ub300\uc2e0 \ud55c \uc5f0\uad6c\uc5d0\uc11c \uc81c\uc2dc\ub41c <strong>lazy update<\/strong> \ud734\ub9ac\uc2a4\ud2f1 \ubc29\ubc95\uc744 \ud65c\uc6a9\ud574 \ubcfc \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Lazy Updating<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774 \ud734\ub9ac\uc2a4\ud2f1 \ubc29\ubc95\uc744 \ud65c\uc6a9\ud558\uae30 \uc804\uc5d0 \ucd08\uae30 \ub178\ub4dc \uc904\uc138\uc6b0\uae30\ub97c \uc774\ubbf8 \ub05d\ub0b4\ub1a8\ub2e4\uace0 \uc0dd\uac01\ud574\ubcf4\uc790. \uc774\uc81c Priority Queue\uc5d0\uc11c \uac00\uc7a5 \ub0ae\uc740 \uc21c\uc704\uc758 \ub178\ub4dc\ub97c \uaebc\ub0b4 \uc21c\uc11c\ub300\ub85c Contraction\ud558\ub294 \uacfc\uc815\uc5d0 \ub4e4\uc5b4\uac04\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ucc28\uc21c\uc73c\ub85c \ub0ae\uc740 \uc21c\uc704\uc758 Node\ub97c Contraction\ud558\uae30 \uc804\uc5d0 \uc774 \ub178\ub4dc\uc758 Edge Difference\ub97c \uacc4\uc0b0\ud55c\ub2e4. \uacc4\uc0b0\ub41c \uac12\uc774 \uc5ec\uc804\ud788 Priority Queue \uc0c1\uc758 \ucd5c\uc18c\uac12\uc774\uba74 Contraction\uc744 \uc2e4\uc81c \uc218\ud589\ud558\uace0 \ub9cc\uc57d \uacc4\uc0b0\ub41c Edge Difference\uac00 \ucd5c\uc18c\uac12\uc774 \uc544\ub2c8\uba74 \uc774 \ub178\ub4dc\uc758 Cost\ub97c \uac31\uc2e0\ud558\uace0 Priority Queue\ub97c \uc7ac\uc815\ub82c\ud55c\ub2e4. \uadf8\ub7f0 \ub2e4\uc74c \ucd5c\uc18c \ub178\ub4dc\ub97c \uccb4\ud06c\ud558\uba70 \uc774 \uacfc\uc815\uc744 \uc774\uc5b4 \ub098\uac04\ub2e4. \uc774 Lazy Updating \ubc29\ubc95\uc744 \uc801\uc6a9\ud560 \uacbd\uc6b0 \ud5a5\uc0c1\ub41c Contraction \uc21c\uc11c\ub85c \uc778\ud574 \ud0d0\uc0c9\uc2dc\uac04 \uac1c\uc120\uc73c\ub85c \uc774\uc5b4\uc9c4\ub2e4\ub294 \uc5f0\uad6c\uac00 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Priority Queue\uc758 Cost \uac12\uc744 \uac31\uc2e0\ud558\uae30 \uc704\ud55c \ub610 \ub2e4\ub978 \ud734\ub9ac\uc2a4\ud2f1 \ubc29\ubc95\uc73c\ub85c \uac00\uc7a5 \ucd5c\uadfc\uc5d0 Contract\ub41c \ub178\ub4dc\uc640 \uc774\uc6c3\ud558\ub294\ub178\ub4dc\uc758 Edge Difference\ub9cc\uc744 \uacc4\uc0b0\ud574\ubcf4\ub294 \ubc29\ubc95\uc774\ub2e4. \uc774\ud6c4 \uc774\uc5b4\uc9c0\ub294 \uacfc\uc815\uc5d0\uc11c lazy update\uac00 \uacfc\ub3c4\ud558\uac8c \ubc1c\uc0dd\ud560 \uacbd\uc6b0 \uc804\uccb4\uc801\uc73c\ub85c \ub0a8\uc544\uc788\ub294 \ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uc5d0 \ub300\ud55c Edge Difference\ub97c \uc7ac\uacc4\uc0b0\ud574\uc57c \ud560 \uc218\ub3c4 \uc788\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\uadf8 \uc678\uc758 Cost Function<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Contraction\uc5d0 \ub4dc\ub294 \ube44\uc6a9 \uacb0\uc815\uc5d0 \ud65c\uc6a9\ub418\ub294 \ub610 \ub2e4\ub978 \uc694\uc18c\ub97c \uace0\ub824\ud574 \ubcfc \uc218 \uc788\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \ub178\ub4dc\ub97c Contraction\ud560 \ub54c \uade0\uc77c\uc131(uniformity)\uacfc \uac19\uc740 \uc544\uc774\ub514\uc5b4\ub97c \uc911\uc694\ud558\uac8c \uace0\ub824\ud574 \ubcfc \uc218 \uc788\ub2e4. \uc774\ub294 Contraction \uc9c4\ud589 \uc21c\uc11c \uad00\uc810\uc5d0\uc11c \ub178\ub4dc\uc758 \uc704\uce58\uc5d0 \ubcc0\ud654\ub97c \uc8fc\ub294 \uac83\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uac1c\ub150\uc801\uc73c\ub85c \uadf8\ub798\ud504\uc0c1\uc5d0\uc11c \uc881\uc740 \uc9c0\uc5ed\uc5d0 \ud3ec\ud568\ub418\uc5b4 \uc788\ub294 \ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uc744 \uc5f0\uc18d\uc801\uc73c\ub85c Contraction\ud558\uace0 \uc2f6\uc9c0\ub294 \uc54a\uc744 \uac83\uc774\ub2e4. \uc65c\ub0d0\ud558\uba74 \ubd88\ud544\uc694\ud55c \uc9c0\ub984\uae38 Edge\ub4e4\uc774 \ub108\ubb34 \ub9ce\uc774 \ud3ec\ud568\ub420 \uc704\ud5d8\uc774 \uc788\uae30 \ub54c\ubb38\uc774\ub2e4. \ucd08\uae30 \uc608\uc81c\uc5d0\uc11c \ube44\uad50\uc801 \uc88b\uc740 \ub178\ub4dc \uc21c\uc11c\ub97c \ubd80\uc5ec\ud588\uc5c8\ub2e4. \uc774\ub294 \uac01 Contraction \ub2e8\uacc4\uc5d0\uc11c \uadf8\ub798\ud504\uc0c1 \uc11c\ub85c \ub2e4\ub978 \uc601\uc5ed\uc5d0\uc11c\uc758 \ub178\ub4dc\ub4e4\uc774 Contraction\ub418\uc5c8\uae30 \ub54c\ubb38\uc774\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub530\ub77c\uc11c \ucd94\uac00\uc801\uc73c\ub85c \uace0\ub824\ud574 \ubcfc\ub9cc\ud55c \uc810\uc740 \uac01 \ub178\ub4dc\uc758 \uc774\uc6c3 \ub178\ub4dc \uc911 Contract\ub41c \uc774\uc6c3 \ub178\ub4dc(contracted neighbors) \uac2f\uc218\ub97c \ub530\uc838\ubcf4\ub294 \uac83\uc774\ub2e4. \uc774\ub294 \uc6d0\ubcf8 \uadf8\ub798\ud504\uc5d0\uc11c \uc774\ubbf8 Contract\ub41c \ub178\ub4dc\ub4e4\uc758 \uac2f\uc218\ub97c \uce74\uc6b4\ud305\ud558\ub294 \uac83\uc774\ub2e4. Cost\ub97c \uacb0\uc815\ud558\ub294 \uacfc\uc815\uc5d0\uc11c <em>Contracted Neighbors<\/em>\uc640 <em>Edge Difference<\/em>\uc640 \uac19\uc774 \uc5ec\ub7ec \uace0\ub824 \uc694\uc18c\uac00 \uc788\uc744 \ub54c  \uc774\ub4e4\uc744 \uc870\ud569\ud558\ub294(<a href=\"https:\/\/en.wikipedia.org\/wiki\/Linear_combination\">\uc120\ud615\uacb0\ud569<\/a>) \ubc29\ubc95\uc744 \uc801\uc6a9\ud55c\ub2e4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\ub178\ub4dc \uc904\uc138\uc6b0\uae30\uc5d0 \uc0ac\uc6a9\ub418\ub294 \uac1c\uc120\ub41c \ud734\ub9ac\uc2a4\ud2f1<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">CH\uad00\ub828 \ub17c\ubb38 \uc6d0\ubb38\uc5d0\uc11c \ub178\ub4dc \uc21c\uc11c\ub97c \uacb0\uc815\ud560 \ub54c \ub354\uc6b1 \uc815\uad50\ud55c \ud56d\ubc95\ub4e4\uc744 \uc0ac\uc6a9\ud558\uace0 \uc788\uc9c0\ub9cc \uc774 \uae00\uc5d0\uc11c\ub294 \ub2e4\ub8e8\uc9c0 \uc54a\ub294\ub2e4. \uc88b\uc740 \uc131\ub2a5\uc758 \ub178\ub4dc \uc904\uc138\uc6b0\uae30\ub294 Edge  difference\uc640 Contracted neighbors\ub97c \ubaa8\ub450 \uc870\ud569\ud55c \ud615\ud0dc\ub85c \ud65c\uc6a9\ud55c\ub2e4. \ub178\ub4dc \uc904\uc138\uc6b0\uae30\uac00 \uc798 \ub418\uc5b4 \uc788\uc73c\uba74 \ud0d0\uc0c9\uc2dc\uac04\uc744 \uc904\uc77c \uc218 \uc788\uc9c0\ub9cc \uc804\ucc98\ub9ac \ub2e8\uacc4\uc5d0\uc11c \ub354 \ub9ce\uc740 \ube44\uc6a9\uc744 \uc9c0\ubd88\ud558\uac8c \ub418\ubbc0\ub85c \uc774 \ub458\uc758 \uad00\uacc4\uc5d0\ub294 Tradeoff \uac00 \uc874\uc7ac\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub7ec\ub098 \uc694\uc57d\ud574\ubcf4\uc790\uba74 Lazy Update \ud734\ub9ac\uc2a4\ud2f1\uc5d0\uc11c \uc18c\uac1c\ud55c \ub450 \uac1c\uc758 \uac1c\ub150\uc740 CH\ub97c \uc801\uc6a9\ud574\ubcf4\uae30\uc5d0 \uc88b\uc740 \uae30\ubc18\uc744 \uc81c\uacf5\ud55c\ub2e4.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\uc55e\uc11c \uae38\ucc3e\uae30 \uc54c\uace0\ub9ac\uc998 \uad00\ub828\ud574\uc11c 2\uac1c\uc758 \uc54c\uace0\ub9ac\uc998(Dijkstra, BidirectionalDijkstra)\uc5d0 \ub300\ud574 \uc0b4\ud3b4\ubd24\ub2e4. \ucef4\ud4e8\ud130\ub97c \ud65c\uc6a9\ud558\uc5ec \uae38\uc744 \ucc3e\uc544\uac00\ub294 \uc54c\uace0\ub9ac\uc998\uc758 \ubaa9\uc801\uc740 \ud06c\uac8c \ucd5c\uc801\uc758 \uacbd\ub85c\ub97c \ucd5c\ub300\ud55c \ube68\ub9ac \ucc3e\uc544\ub0b4\ub294 \uac83\uc774\ub77c \ud560 \uc218 \uc788\ub2e4. \uc774\ub860\uc801\uc73c\ub85c \uc774\ub4e4 \uc54c\uace0\ub9ac\uc998\uc740 \ucd5c\uc801\uc758 \uacbd\ub85c\ub97c \ucc3e\uc544\uc8fc\ub294 \uac83\uc744 \ubcf4\uc7a5\ud558\uc9c0\ub9cc \ucd5c\ub300\ud55c \ube68\ub9ac \ucc3e\ub294 \uac83\uc5d0\ub294 \ud55c\uacc4\ub97c \ub4dc\ub7ec\ub0b4\uace0 \uc788\ub2e4. \uc55e\uc5d0\uc11c \uc124\uba85\ud55c BidirectionalDijkstra \uc54c\uace0\ub9ac\uc998\ub3c4 \uc774\ub7f0 \ub9e5\ub77d\uc5d0\uc11c \ud0d0\uc0c9\uc18d\ub3c4\ub97c \uac1c\uc120\ud558\uae30 \uc704\ud55c \ud558\ub098\uc758 \ubc29\ubc95\uc73c\ub85c \ubcfc \uc218 \uc788\ub2e4. \uc774\ucc98\ub7fc Dijkstra Algorithm\uc758 \ud0d0\uc0c9 \uc18d\ub3c4\ub294 \ud0d0\uc0c9\uacf5\uac04 \ud06c\uae30\uc5d0 \uc885\uc18d\uc801\uc77c \uc218 \ubc16\uc5d0 \uc5c6\uc73c\uba70 \ub098\uc544\uac00 \uae38\ucc3e\uae30\uac00 \ud55c \uad6d\uac00\ub97c \ub118\uc5b4 \uae00\ub85c\ubc8c \uaddc\ubaa8\ub85c \ud655\ub300\ud574 \ub098\uac04\ub2e4\uba74 \ud0d0\uc0c9 \uc18d\ub3c4\ub294 \uc11c\ube44\uc2a4 \uacbd\uc7c1\ub825\uc744 \uc720\uc9c0\uc5d0 \uc911\uc694\ud55c&#8230;<\/p>\n<p class=\"read-more\"><a class=\"btn btn-default\" href=\"https:\/\/skanto.co.kr\/?p=1299\"> Read More<span class=\"screen-reader-text\">  Read More<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[14,7],"tags":[136,144,114],"class_list":["post-1299","post","type-post","status-publish","format-standard","hentry","category-sw-development","category-7","tag-bidirectional-dijkstra","tag-contraction-hierarchy","tag-dijkstra"],"_links":{"self":[{"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/1299","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1299"}],"version-history":[{"count":137,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/1299\/revisions"}],"predecessor-version":[{"id":1526,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/1299\/revisions\/1526"}],"wp:attachment":[{"href":"https:\/\/skanto.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1299"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1299"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1299"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}