{"id":3881,"date":"2017-02-01T11:05:58","date_gmt":"2017-02-01T02:05:58","guid":{"rendered":"http:\/\/www.gisdeveloper.co.kr\/?p=3881"},"modified":"2017-02-01T14:57:49","modified_gmt":"2017-02-01T05:57:49","slug":"%ec%b5%9c%eb%8b%a8-%ea%b2%bd%eb%a1%9c-%ed%83%90%ec%83%89-%ec%95%8c%ea%b3%a0%eb%a6%ac%ec%a6%98-dijkstra","status":"publish","type":"post","link":"http:\/\/www.gisdeveloper.co.kr\/?p=3881","title":{"rendered":"\ucd5c\ub2e8 \uacbd\ub85c \ud0d0\uc0c9 &#8211; Dijkstra \uc54c\uace0\ub9ac\uc998"},"content":{"rendered":"<p>\ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc740 \uc2dc\uc791 \ub178\ub4dc\ub9cc\uc744 \uc9c0\uc815\ud558\uba74, \uc774 \uc2dc\uc791 \ub178\ub4dc\uc5d0\uc11c\u00a0\ub2e4\ub978 \ubaa8\ub4e0 \ub178\ub4dc\uc5d0 \ub300\ud55c \ucd5c\ub2e8 \uacbd\ub85c\ub4e4\uc744 \ubd84\uc11d\ud574 \uc90d\ub2c8\ub2e4. \ucc38\uace0\ub85c \ucd5c\ub2e8 \uacbd\ub85c \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc758 \ub2e4\ub978\u00a0\ud615\ud0dc\ub85c\u00a0\u00a0A*(\uc5d0\uc774\uc2a4\ud0c0) \uc54c\uace0\ub9ac\uc998\uc774 \uc788\ub294\ub370\uc694. A* \uc54c\uace0\ub9ac\uc998\uc740 \uc2dc\uc791 \ub178\ub4dc\uc5d0\uc11c \ubaa9\uc801\uc9c0 \ub178\ub4dc\ub97c \uc9c0\uc815\ud574\uc8fc\uba74 \uc774 2\uac1c\uc758 \ub178\ub4dc \uac04\uc758 \ucd5c\ub2e8 \uacbd\ub85c \ud558\ub098\ub9cc\uc744 \ubd84\uc11d\ud574 \uc90d\ub2c8\ub2e4.<\/p>\n<p>\uc774 \uae00\uc740 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud55c \uc774\ub7f0 \uc800\ub7f0 \uc7a5\ud669\ud55c \uc124\uba85\uc744 \ubc30\uc81c\ud558\uace0 \uc2e4\uc81c \uc608\ub97c \ub4e4\uc5b4, \uadf8 \uc608\uc5d0 \ub300\ud55c \ucd5c\ub2e8 \uacbd\ub85c \ud0d0\uc0c9\uc744 \uc704\ud55c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \uc124\uba85\ud569\ub2c8\ub2e4.<\/p>\n<p>\uba3c\uc800 \ub2e4\uc74c\uacfc \uac19\uc740 \uc608\ub97c \ub4e4\uc5b4 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-3882\" src=\"http:\/\/www.gisdeveloper.co.kr\/wp-content\/uploads\/2017\/02\/1.png\" alt=\"\" width=\"540\" height=\"505\" \/><\/p>\n<p>\uc704\uc758 \uadf8\ub9bc\uc744 \uac04\ub2e8\ud788 \uc124\uba85\ud558\uba74, 0\ubd80\ud130 6\ubc88\uae4c\uc9c0\uc758 \ub178\ub4dc(Node)\uac00 \uc874\uc7ac\ud558\uace0 \uac01 \ub178\ub4dc\ub97c \uc5f0\uacb0\ud558\ub294 \uc120\uc778 \ub9c1\ud06c(Link)\uac00 \uc788\uc2b5\ub2c8\ub2e4.\u00a0 \uac01 \ub9c1\ud06c\uc5d0\ub294 \uc22b\uc790\uac00 \ud45c\uc2dc\ub418\uc5b4 \uc788\ub294\ub370\uc694. \uc774 \uc22b\uc790\ub294 \ud574\ub2f9 \ub9c1\ud06c\ub97c \uc9c0\ub098\uac08\ub54c\uc5d0 \uc18c\uc694\ub418\ub294 \ube44\uc6a9(Cost, \uacbd\ube44)\ub85c \uc0dd\uac01\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, 2\ubc88 \ub178\ub4dc\uc640 6\ubc88 \ub178\ub4dc \uc0ac\uc774\uc5d0 \ube44\uc6a9\u00a08\uc778\u00a0\ub9c1\ud06c\uac00 \uc788\ub294\ub370\uc694. \uc774\ub294 2\ubc88 \ub178\ub4dc\uc5d0\uc11c 6\ubc88 \ub178\ub4dc\ub97c \uc9c0\ub098\uac04\ub2e4\uace0 \ud560\ub54c 8\uc758 \ube44\uc6a9\uc774 \ud544\uc694\ud558\ub2e4\ub294 \uc758\ubbf8\uc785\ub2c8\ub2e4. \ube44\uc6a9\uc774 \uc801\uc744 \uc218\ub85d \uc0c1\ub300\uc801\uc73c\ub85c \ub354 \uc88b\uc740 \uacbd\ub85c\uc774\uaca0\uc9c0\uc694.<\/p>\n<p>\uc774\uc81c \uc704\uc758 \uc608, \uc989 0\ubc88 \ub178\ub4dc\ub97c \uc2dc\uc791\uc810\uc73c\ub85c \ud574\uc11c \ub098\uba38\uc9c0\u00a0\u00a01, 2, 3, 4, 5, 6 \ubc88 \ub178\ub4dc\ub97c \ubaa9\uc801\uc9c0\ub85c \ud558\ub294 \ucd5c\ub2e8 \uacbd\ub85c 6\uac1c\ub97c \uad6c\ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc774 \ubc14\ub85c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4.<\/p>\n<p>\uc774\uc0c1\uc758 \ubb38\uc81c \ud574\uacb0\uc744 \uc704\ud574 \uac00\uc7a5 \uba3c\uc800 \uc2dc\uc791\ub418\ub294 \uc5f0\uc0b0\uc740 \ub2e4\uc74c \uadf8\ub9bc\uacfc \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-3884\" src=\"http:\/\/www.gisdeveloper.co.kr\/wp-content\/uploads\/2017\/02\/2.png\" alt=\"\" width=\"1096\" height=\"399\" \/><\/p>\n<p>\uc704\uc758 \uadf8\ub9bc\uc5d0\uc11c S \uc740 \uc774\ubbf8 \ucc98\ub9ac\uac00 \uc644\uacb0\ub41c \ub178\ub4dc\uc758 \uc9d1\ud569\uc778\ub370\uc694. \uac00\uc7a5 \uba3c\uc800 \uc2dc\uc791 \ub178\ub4dc\uc778 0\ubc88\uc744 \uc9d1\uc5b4 \ub193\uc74c\uc73c\ub85c\uc368 0\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud55c \ucc98\ub9ac\ub97c \uc2dc\uc791\ud569\ub2c8\ub2e4. D \uc800\uc7a5\uc18c\ub294 0\ubc88~6\ubc88\uae4c\uc9c0\uc758 \ub178\ub4dc\uc5d0 \ub300\ud574, \uc2dc\uc791\ub178\ub4dc\ub85c\ubd80\ud130 \uc18c\uc694\ub418\ub294 \ube44\uc6a9\uc744 \uc800\uc7a5\ud558\uace0 \uc788\uc2b5\ub2c8\ub2e4. D \uc800\uc7a5\uc18c\uc758 \uc0c1\ub2e8 \ud589\uc740 \ub178\ub4dc\uc758 \ubc88\ud638\uc774\uace0 \ud558\ub2e8 \ud589\uc740 \uc2dc\uc791\ub178\ub4dc\ub85c\ubd80\ud130 \uc18c\uc694\ub418\ub294 \ube44\uc6a9\uc785\ub2c8\ub2e4. \uc704 \uadf8\ub9bc\uc5d0\uc11c\u00a0D \uc800\uc7a5\uc18c\ub97c \ubcf4\uba74 0\ubc88 \ub178\ub4dc\ub294 \uc2dc\uc791\ub178\ub4dc\uc774\ubbc0\ub85c \uc18c\uc694\ub418\ub294 \ube44\uc6a9\uc774 0\uc774\uace0, 0\ubc88 \ub178\ub4dc\uc640 \ub9c1\ud06c\ub85c\u00a0\uc5f0\uacb0\ub41c 1\ubc88\uacfc 3\ubc88 \ub178\ub4dc\ub294 \uac01\uac01 5\uc640 1\uc758 \ube44\uc6a9\uc774 \uc18c\uc694\ub418\ub294 \uac83\uc73c\ub85c \uae30\ub85d\ub418\uc5b4 \uc788\uc2b5\ub2c8\ub2e4. T \uc800\uc7a5\uc18c\ub294 \ud574\ub2f9 \ub178\ub4dc\ub85c \uac00\ub294\ub370 \uc5f0\uacb0\ub41c \ub178\ub4dc\uc758 \ubc88\ud638\ub97c\u00a0\ub2f4\uace0 \uc788\ub294\ub370\uc694.\u00a0T \uc800\uc7a5\uc18c\uc774 \uc0c1\ub2e8 \ud589\uc740 \ub178\ub4dc\uc758 \ubc88\ud638\uc774\uace0 \ud558\ub2e8 \ub178\ub4dc\ub294 \uc5f0\uacb0\ub41c \ub178\ub4dc \ubc88\ud638\uc785\ub2c8\ub2e4. \uc704\uc758 \uadf8\ub9bc\uc744 \ubcf4\uba74 1\ubc88 \ub178\ub4dc\uc640 3\ubc88 \ub178\ub4dc\ub294 0\ubc88 \ub178\ub4dc\uc640 \uc5f0\uacb0\ub418\uc5b4 \uc788\uc73c\ubbc0\ub85c 0\uc73c\ub85c \uae30\ub85d\ub418\uc5b4\uc838 \uc788\uc2b5\ub2c8\ub2e4. \uc774\uac8c\u00a0\uc8fc\uc5b4\uc9c4 \ubb38\uc81c\uc5d0 \ub300\ud55c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc758 \uccab\ubc88\uc9f8\u00a0\ucc98\ub9ac\uc785\ub2c8\ub2e4.<\/p>\n<p>\uc774\uc81c \ub2e4\uc74c \ucc98\ub9ac\uc5d0 \ub300\ud55c \uadf8\ub9bc\uc744 \uc0b4\ud3b4 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-3885\" src=\"http:\/\/www.gisdeveloper.co.kr\/wp-content\/uploads\/2017\/02\/3.png\" alt=\"\" width=\"1096\" height=\"399\" \/><\/p>\n<p>S\uc9d1\ud569\uc5d0 3\ubc88 \ub178\ub4dc\ub97c \ucd94\uac00\ud588\uc2b5\ub2c8\ub2e4. \uc774\uc720\ub294 D \uc800\uc7a5\uc18c\uc5d0 3\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud55c \ube44\uc6a9\uac12\uc774 \uac00\uc7a5 \ucd5c\uc18c\uc774\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4. S\uc9d1\ud569\uc5d0 3\ubc88 \ub178\ub4dc\ub97c \ucd94\uac00\ud568\uc73c\ub85c\uc368 3\ubc88 \ub178\ub4dc\uc640 \ub9c1\ud06c\ub85c \uc5f0\uacb0\ub41c 2\ubc88\uacfc 5\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud55c \ube44\uc6a9\uac12\uc744 \uacc4\uc0b0\ud574 D \uc800\uc7a5\uc18c\uc5d0 \uae30\ub85d\ud574\uc57c \ud558\ub294\ub370\uc694. \uc2dc\uc791 \ub178\ub4dc\uc778 0\ubc88 \ub178\ub4dc\uc5d0\uc11c 2\ubc88 \ub178\ub4dc\uae4c\uc9c0 \uac00\uae30 \uc704\ud574\uc11c \uc18c\uc694\ub418\ub294 \ube44\uc6a9\uc740 \ucd1d 3\uc785\ub2c8\ub2e4. \uc774\uc720\ub294 0\ubc88-3\ubc88-2\ubc88 \ub178\ub4dc\ub85c \uac00\uc57c\ud558\ubbc0\ub85c \ube44\uc6a9\uac12\uc740 0\ubc88-3\ubc88 \ub178\ub4dc\ub85c \uac00\ub294 \ube44\uc6a9 1\uacfc 3\ubc88\uacfc 2\ubc88 \ub178\ub4dc\ub85c \uac00\ub294 \ube44\uc6a9 2\ub97c \ud569\ud55c \uac12\uc785\ub2c8\ub2e4. \uc774\ub7ec\ud55c \uacc4\uc0b0\uc740 D \uc800\uc7a5\uc18c\ub97c \ud65c\uc6a9\ud558\uba74 \uc27d\uac8c \uacc4\uc0b0\ud560 \uc218 \uc788\ub294\ub370\uc694. \uc774\ubbf8 \uc2dc\uc791\ub178\ub4dc\uc5d0\uc11c \uac01 \ub178\ub4dc\ub85c \uac00\ub294 \ube44\uc6a9\uc774 \uacc4\uc0b0\ub418\uc5b4 \uc788\uae30 \ub54c\ubb38\uc5d0 \ub9c8\uc9c0\ub9c9 \ub178\ub4dc\ub85c \uac00\ub294 \ube44\uc6a9\ub9cc\uc744 \ub354\ud574\uc8fc\uba74 \ub418\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4. 5\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud55c \ube44\uc6a9\uc740 \ub3d9\uc77c\ud55c \ubc29\uc2dd\uc73c\ub85c 1+1\uc778 2\uac00 \ub429\ub2c8\ub2e4. \uadf8\ub9ac\uace0 T \uc800\uc7a5\uc18c\ub3c4 \uac01 \ub178\ub4dc\uc5d0 \ub300\ud574 \uc774\uc804\uc5d0 \uc5f0\uacb0\ub41c \ub178\ub4dc\uac12\uc744 \uae30\ub85d\ud574 \ub461\ub2c8\ub2e4. T \uc800\uc7a5\uc18c\uc758 2\ubc88\uacfc 5\ubc88 \ub178\ub4dc\ub294 3\ubc88 \ub178\ub4dc\ub97c \ud1b5\ud574 \uc5f0\uacb0\ub418\uc5b4 \uc788\uc73c\ubbc0\ub85c\u00a03\uc744 \uae30\ub85d\ud569\ub2c8\ub2e4. \ub2e4\uc74c \ucc98\ub9ac\uc5d0 \ub300\ud55c \uadf8\ub9bc\uc744 \uc0b4\ud3b4\ubd05\uc2dc\ub2e4.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-3888\" src=\"http:\/\/www.gisdeveloper.co.kr\/wp-content\/uploads\/2017\/02\/4.png\" alt=\"\" width=\"1096\" height=\"399\" \/><\/p>\n<p>S \uc9d1\ud569\uc5d0 5\ub97c \ucd94\uac00\ud588\uc2b5\ub2c8\ub2e4. \uc774\ub294 \uc774\ubbf8 \ucc98\ub9ac\uac00 \uc644\ub8cc\ub41c \ub178\ub4dc \uc774\uc678\uc758 \ub178\ub4dc \uc911 5\ubc88 \ub178\ub4dc\uc758 \ube44\uc6a9\uc774 2\ub85c \uac00\uc7a5 \ucd5c\uc18c\uc774\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4.\u00a0 \uc774\ubbf8 \ucc98\ub9ac\uac00 \uc644\ub8cc\ub41c \ub178\ub4dc\uc778\uc9c0 S \uc9d1\ud569\uc5d0 \uc874\uc7ac\ud558\ub294\uc9c0\ub97c \ubcf4\uba74 \uc54c \uc218 \uc788\uc2b5\ub2c8\ub2e4. 5\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud574 \uc5f0\uacb0\ub41c \ub178\ub4dc\ub294 2, 3, 6\ubc88 \ub178\ub4dc\uc778\ub370\uc694. \uc774\ubbf8 3\ubc88\uc740 \ucc98\ub9ac\uac00 \uc644\ub8cc\ub418\uc5c8\uc73c\ubbc0\ub85c 2\ubc88 \ub178\ub4dc\uc640 3\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud574 D \uc800\uc7a5\uc18c\uc758 \uac12\uc744 \uac31\uc2e0\ud574\uc57c \ud569\ub2c8\ub2e4. 5\ubc88 \ub178\ub4dc\ub97c \uac70\uccd0 2\ubc88 \ub178\ub4dc\ub97c \uac08 \uacbd\uc6b0 \uc18c\uc694\ub418\ub294 \ube44\uc6a9\uc740 2+2\ub85c 4\uc785\ub2c8\ub2e4. \uc774 \uac12\uc740 \uc774\ubbf8 \uc804 \ub2e8\uacc4\uc5d0\uc11c \uacc4\uc0b0\ub41c \ube44\uc6a9\uac12(3)\ubcf4\ub2e4 \ud06c\ubbc0\ub85c \ubb34\uc2dc\ud569\ub2c8\ub2e4. 6\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud55c \ube44\uc6a9\uac12\uc740 5\ubc88 \ub178\ub4dc\uae4c\uc9c0 \uc624\ub294\ub370 \uc18c\uc694\ub41c \ube44\uc6a9\uac12(2)\uc640 5\ubc88\uc5d0\uc11c 6\ubc88 \ub178\ub4dc\ub85c \uac00\ub294\ub370 \ucd94\uac00\uc801\uc73c\ub85c \ud544\uc694\ud55c \ube44\uc6a9 3\uc744 \ud569\ud55c\u00a0\uac12 5\uc774\ubbc0\ub85c, \uc774 \uac12\uc744 D \uc800\uc7a5\uc18c\uc5d0 \uae30\ub85d\ud558\uace0 T \uc800\uc7a5\uc18c\uc758 6\ubc88 \ub178\ub4dc \uac12\uc5d0 5\ubc88\u00a0\ub178\ub4dc\ub97c \uae30\ub85d\ud569\ub2c8\ub2e4.\u00a0\ub2e4\uc74c \ub2e8\uacc4\ub85c \ub118\uc5b4 \uac11\ub2c8\ub2e4.\u00a0<img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-3889\" src=\"http:\/\/www.gisdeveloper.co.kr\/wp-content\/uploads\/2017\/02\/5.png\" alt=\"\" width=\"1096\" height=\"399\" \/><\/p>\n<p>\ucc98\ub9ac\uac00 \uc644\uacb0\ub418\uc9c0\u00a0\uc54a\uc740 \ub178\ub4dc \uc911 \ube44\uc6a9\uc774 \ucd5c\uc18c\uc778 \ub178\ub4dc\ub294 2\ubc88\uc778\ub370\uc694. 2\ubc88 \ub178\ub4dc\uc640 \uc5f0\uacb0\ub41c \ub178\ub4dc\ub294 1, 3, 5, 6\ubc88 \ub178\ub4dc\uc785\ub2c8\ub2e4. \ucc98\ub9ac\uac00 \uc644\uacb0\ub41c \ub178\ub4dc\ub97c \uc800\uc7a5\ud558\uace0 \uc788\ub294 S \uc9d1\ud569\uc744 \ud1b5\ud574 3\ubc88 \ub178\ub4dc\uc640 5\ubc88 \ub178\ub4dc\ub294 \ub354 \uc774\uc0c1 \uace0\ub824\ud560 \ud544\uc694\uac00 \uc5c6\ub2e4\ub294 \uac83\uc744 \uc54c \uc218 \uc788\uc73c\ub2c8, 1, 6\ubc88\ub9cc \uace0\ub824\ud558\uba74 \ub429\ub2c8\ub2e4. \uba3c\uc800 1\ubc88\uc758 \uacbd\uc6b0 \uc18c\uc694\ub418\ub294 \ube44\uc6a9\uc740 3+1\ub85c 4\uc778\ub370\uc694. \uc774 \uac12\uc740 \uc774\uc804 \ub2e8\uacc4\uc5d0\uc11c \uacc4\uc0b0\ub41c \ube44\uc6a9\uac12(5)\ubcf4\ub2e4 \uc791\uc73c\ub85c D \uc800\uc7a5\uc18c\uc758 \uac12\uc744 \ubcc0\uacbd \ud569\ub2c8\ub2e4. D \uc800\uc7a5\uc18c\uac00 \ubcc0\uacbd\ub418\uba74\u00a0 T \uc800\uc7a5\uc18c\uc758 \uac12\ub3c4 2\ubc88 \ub178\ub4dc\ub85c \ubcc0\uacbd\ud569\ub2c8\ub2e4. \uc911\uc694\ud55c \ubd80\ubd84\uc774\ubbc0\ub85c \uc704\uc758 \uadf8\ub9bc\uc5d0\uc11c \ube68\uac04\uc0c9\uc73c\ub85c \ud45c\uc2dc\ud588\uc2b5\ub2c8\ub2e4. \uc774\uc81c \ub0a8\uc740 6\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud55c \ube44\uc6a9\uac12\uc744 \uacc4\uc0b0\ud574 \ubcf4\uba74 3+8\ub85c 11\uc778\ub370\uc694. \uc774 \uac12\uc740 \uc774\uc804 \ub2e8\uacc4\uc5d0\uc11c \uacc4\uc0b0\ub41c \ube44\uc6a9\uc778 5\ubcf4\ub2e4 \ud06c\ubbc0\ub85c \ubb34\uc2dc\ud569\ub2c8\ub2e4. \ub2e4\uc74c \ub2e8\uacc4\ub85c \uc9c4\ud589\ud569\ub2c8\ub2e4.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-3890\" src=\"http:\/\/www.gisdeveloper.co.kr\/wp-content\/uploads\/2017\/02\/6.png\" alt=\"\" width=\"1096\" height=\"399\" \/><\/p>\n<p>\ucc98\ub9ac\uac00 \uc644\ub8cc\ub41c \ub178\ub4dc\uac00 \uc544\ub2cc \uac83 \uc911 1\ubc88 \ub178\ub4dc\uc758 \ube44\uc6a9\uc774 \ud604\uc7ac \uac00\uc7a5 \ucd5c\uc18c\uc774\ubbc0\ub85c \uc9d1\ud569 S\uc5d0 1\ubc88 \ub178\ub4dc\ub97c \ucd94\uac00\ud558\uace0 1\ubc88 \ub178\ub4dc\uc640 \uc5f0\uacb0\ub41c 0, 2, 4\ubc88 \ub178\ub4dc \uc911 \uc644\uacb0\ub418\uc9c0 \uc54a\uc740 4\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud55c \ube44\uc6a9\uac12\uc744 \uacc4\uc0b0\ud569\ub2c8\ub2e4. 4\ubc88 \ub178\ub4dc\uc758 \ube44\uc6a9\uac12\uc740 4+3\uc73c\ub85c 7\uc774\ubbc0\ub85c \uc774 \uac12\uc744 D \uc800\uc7a5\uc18c\uc5d0 \uae30\ub85d\ud558\uace0 T \uc800\uc7a5\uc18c\uc5d0 1\ubc88 \ub178\ub4dc\ub97c \uae30\ub85d\ud569\ub2c8\ub2e4.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-3891\" src=\"http:\/\/www.gisdeveloper.co.kr\/wp-content\/uploads\/2017\/02\/7.png\" alt=\"\" width=\"1097\" height=\"399\" \/><\/p>\n<p>\uc774\ubbf8 \ucc98\ub9ac\uac00 \uc644\ub8cc\ub41c \ub178\ub4dc\uac00 \uc544\ub2cc \uac83 \uc911 \ucd5c\uc18c\uc778 \ub178\ub4dc\ub294 6\ubc88 \ub178\ub4dc\uc778\ub370\uc694. \uc774 6\ubc88 \ub178\ub4dc\ub97c \uc9d1\ud569 S\uc5d0 \ucd94\uac00\ud558\uace0 6\ubc88 \ub178\ub4dc\uc640 \ub9c1\ud06c\ub85c \uc5f0\uacb0\ub41c \u00a01, 2, 4, 5\u00a0\uc911 \ucc98\ub9ac\uac00 \uc644\uacb0\ub418\uc9c0 \uc54a\uc740 \ub178\ub4dc\ub294 4\ubc88\uc778\ub370\uc694. 6\ubc88 \ub178\ub4dc\ub97c \uacbd\uc720\ud574 4\ubc88 \ub178\ub4dc\ub85c \uac00\uae30 \uc704\ud55c \ube44\uc6a9\uc740 5 + 1\uc778 6\uc73c\ub85c \uacc4\uc0b0\ub418\uba70, \uc774 \uac12\uc740 \uc774\uc804 \ub2e8\uacc4\uc5d0\uc11c \uacc4\uc0b0\ub41c \uac12(7)\ubcf4\ub2e4 \uc791\uc73c\ubbc0\ub85c D \uc800\uc7a5\uc18c\uac00 \ubcc0\uacbd\ub418\uace0, \uc774\uc640 \ud568\uaed8 T \uc800\uc7a5\uc18c\uc5d0 \ub300\ud574\uc11c\ub3c4 4\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud574 6\ubc88 \ub178\ub4dc\ub85c \ubcc0\uacbd\ud569\ub2c8\ub2e4. \u00a0\ub2e4\uc74c \ub2e8\uacc4\ub85c \uc9c4\ud589\ud569\ub2c8\ub2e4.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-3893\" src=\"http:\/\/www.gisdeveloper.co.kr\/wp-content\/uploads\/2017\/02\/8.png\" alt=\"\" width=\"1096\" height=\"399\" \/><\/p>\n<p>\ucc98\ub9ac\ub418\uc9c0 \uc54a\uc740 \ub178\ub4dc \uc911, \uc774\uc81c \uc720\uc77c\ud558\uac8c 4\ubc88 \ub178\ub4dc\ub9cc \ub0a8\uc558\ub294\ub370\uc694. 4\ubc88 \ub178\ub4dc\uc640 \uc5f0\uacb0\ub41c 1, 6\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud574 \ucc98\ub9ac\ub97c \ud574\uc57c \ud558\ub294\ub370 \uc774\ubbf8 1, 6\ubc88 \ub178\ub4dc\ub294 \ucc98\ub9ac\uac00 \uc644\uacb0\ub418\uc5c8\uc73c\ubbc0\ub85c \ub354 \uc774\uc0c1 \uc9c4\ud589\ud558\uc9c0 \uc54a\uace0 \uc885\ub8cc\ub429\ub2c8\ub2e4.<\/p>\n<p>\uc774\uc0c1\uc758 \uacb0\uacfc\uc5d0\uc11c T \uc800\uc7a5\uc18c\ub97c \ud1b5\ud574 \ucd9c\ubc1c \ub178\ub4dc\uc778 0\ubc88 \ub178\ub4dc\uc5d0\uc11c \uac01 \ub178\ub4dc\uc5d0 \ub300\ud55c \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ud30c\uc545\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. 0\ubc88 \ub178\ub4dc\uc5d0\uc11c 1\ubc88 \ub178\ub4dc\uc5d0 \ub300\ud55c \ucd5c\ub2e8 \uacbd\ub85c\ub294 <strong>(1\ubc88 \ub178\ub4dc)\u2190(2\ubc88 \ub178\ub4dc)\u2190(3\ubc88 \ub178\ub4dc)\u2190(0\ubc88 \ub178\ub4dc)<\/strong>\uac00 \ub429\ub2c8\ub2e4. \uc774\ub294 T \uc800\uc7a5\uc18c\ub97c \ubcf4\uba74, \uba3c\uc800 1\ubc88 \ub178\ub4dc\uc5d0 \uc5f0\uacb0\ub418\ub294 \ub178\ub4dc\ub294 2\ubc88 \ub178\ub4dc\ub77c\ub294 \uac83\uc744 \uc54c \uc218 \uc788\uace0, \ub2e4\uc2dc 2\ubc88 \ub178\ub4dc\ub294 3\ubc88 \ub178\ub4dc\uc640 \uc5f0\uacb0\ub418\uba70 3\ubc88 \ub178\ub4dc\ub294 \uc2dc\uc791 \ub178\ub4dc\uc778 0\ubc88 \ub178\ub4dc\ub77c\uace0 \uae30\ub85d\ub418\uc5b4 \uc788\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4. \uc2dc\uc791 \ub178\ub4dc 0\ubc88\uc5d0\uc11c \uac01 \ub178\ub4dc\uc5d0 \ub300\ud55c \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uc815\ub9ac\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<ul>\n<li>0\ubc88 \ub178\ub4dc\uc5d0\uc11c 1\ubc88 \ub178\ub4dc : <strong>(1\ubc88 \ub178\ub4dc)\u2190(2\ubc88 \ub178\ub4dc)\u2190(3\ubc88 \ub178\ub4dc)\u2190(0\ubc88 \ub178\ub4dc)<\/strong><\/li>\n<li>0\ubc88 \ub178\ub4dc\uc5d0\uc11c 2\ubc88 \ub178\ub4dc :\u00a0<strong>(2\ubc88 \ub178\ub4dc)\u2190(3\ubc88 \ub178\ub4dc)\u2190(0\ubc88 \ub178\ub4dc)<\/strong><\/li>\n<li>0\ubc88 \ub178\ub4dc\uc5d0\uc11c 3\ubc88 \ub178\ub4dc :\u00a0<strong>(3\ubc88 \ub178\ub4dc)\u2190(0\ubc88 \ub178\ub4dc)<\/strong><\/li>\n<li>0\ubc88 \ub178\ub4dc\uc5d0\uc11c 4\ubc88 \ub178\ub4dc : <strong>(4\ubc88 \ub178\ub4dc)\u2190(6\ubc88 \ub178\ub4dc)\u2190(5\ubc88 \ub178\ub4dc)\u2190(3\ubc88 \ub178\ub4dc)\u2190(0\ubc88 \ub178\ub4dc)<\/strong><\/li>\n<li>0\ubc88 \ub178\ub4dc\uc5d0\uc11c 5\ubc88 \ub178\ub4dc :\u00a0<strong>(5\ubc88 \ub178\ub4dc)\u2190(3\ubc88 \ub178\ub4dc)\u2190(0\ubc88 \ub178\ub4dc)<\/strong><\/li>\n<li>0\ubc88 \ub178\ub4dc\uc5d0\uc11c 6\ubc88 \ub178\ub4dc :\u00a0<strong>(6\ubc88 \ub178\ub4dc)\u2190<\/strong><strong>(5\ubc88 \ub178\ub4dc)\u2190(3\ubc88 \ub178\ub4dc)\u2190(0\ubc88 \ub178\ub4dc)<\/strong><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc740 \uc2dc\uc791 \ub178\ub4dc\ub9cc\uc744 \uc9c0\uc815\ud558\uba74, \uc774 \uc2dc\uc791 \ub178\ub4dc\uc5d0\uc11c\u00a0\ub2e4\ub978 \ubaa8\ub4e0 \ub178\ub4dc\uc5d0 \ub300\ud55c \ucd5c\ub2e8 \uacbd\ub85c\ub4e4\uc744 \ubd84\uc11d\ud574 \uc90d\ub2c8\ub2e4. \ucc38\uace0\ub85c \ucd5c\ub2e8 \uacbd\ub85c \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc758 \ub2e4\ub978\u00a0\ud615\ud0dc\ub85c\u00a0\u00a0A*(\uc5d0\uc774\uc2a4\ud0c0) \uc54c\uace0\ub9ac\uc998\uc774 \uc788\ub294\ub370\uc694. A* \uc54c\uace0\ub9ac\uc998\uc740 \uc2dc\uc791 \ub178\ub4dc\uc5d0\uc11c \ubaa9\uc801\uc9c0 \ub178\ub4dc\ub97c \uc9c0\uc815\ud574\uc8fc\uba74 \uc774 2\uac1c\uc758 \ub178\ub4dc \uac04\uc758 \ucd5c\ub2e8 \uacbd\ub85c \ud558\ub098\ub9cc\uc744 \ubd84\uc11d\ud574 \uc90d\ub2c8\ub2e4. \uc774 \uae00\uc740 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud55c \uc774\ub7f0 \uc800\ub7f0 \uc7a5\ud669\ud55c \uc124\uba85\uc744 \ubc30\uc81c\ud558\uace0 \uc2e4\uc81c \uc608\ub97c \ub4e4\uc5b4, \uadf8 \uc608\uc5d0 \ub300\ud55c &hellip; <\/p>\n<p class=\"link-more\"><a href=\"http:\/\/www.gisdeveloper.co.kr\/?p=3881\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;\ucd5c\ub2e8 \uacbd\ub85c \ud0d0\uc0c9 &#8211; Dijkstra \uc54c\uace0\ub9ac\uc998&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9,50,8],"tags":[],"class_list":["post-3881","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-gisdev","category-programming"],"_links":{"self":[{"href":"http:\/\/www.gisdeveloper.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/3881","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.gisdeveloper.co.kr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.gisdeveloper.co.kr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.gisdeveloper.co.kr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.gisdeveloper.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3881"}],"version-history":[{"count":7,"href":"http:\/\/www.gisdeveloper.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/3881\/revisions"}],"predecessor-version":[{"id":3887,"href":"http:\/\/www.gisdeveloper.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/3881\/revisions\/3887"}],"wp:attachment":[{"href":"http:\/\/www.gisdeveloper.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3881"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.gisdeveloper.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3881"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.gisdeveloper.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3881"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}