![\"\"\/](\"https:\/\/www.baeldung.com\/wp-content\/uploads\/2017\/01\/step2.png\")
<\/figure>\n\n\n\n\ud3c9\uac00 \uc2dc \ubaa9\uc801\uc9c0 \ub178\ub4dc\uae4c\uc9c0\uc758 \uac70\ub9ac \uacc4\uc0b0\uc740 \ud3c9\uac00\ub178\ub4dc\uc758 \uac70\ub9ac(weight \uc544\ub2d8)\uc640 \ubaa9\uc801\uc9c0 \ub9c1\ud06c\uc758 weight\ub97c \ud569\uc0b0\ud55c \ud6c4 \uadf8 \uac12\uc744 \ubaa9\uc801\uc9c0 \ub178\ub4dc\uc758 \uac70\ub9ac\uc640 \ube44\uad50\ud55c\ub2e4. \uc989, \ub178\ub4dc B\ub97c \uc608\ub85c\ub4e4\uba74 0 * 10\uc740 \ub178\ub4dc B\uc758 \uac70\ub9ac\uc778 \ubb34\ud55c\ub300(infinite) \ubcf4\ub2e4 \uc9e7\ub2e4. \ub530\ub77c\uc11c \ub178\ub4dc B\uae4c\uc9c0\uc758 \uac70\ub9ac\ub294 10\uc73c\ub85c \ub300\uccb4\ub418\uba70 \uc774\uc804 \ub178\ub4dc\ub294 A\uac00 \ub41c\ub2e4. \uc774\uc640 \ub3d9\uc77c\ud55c \uacfc\uc815\uc744 \ub178\ub4dc C\uc5d0\ub3c4 \uc801\uc6a9\ud55c\ub2e4.<\/p>\n\n\n\n
\uadf8\ub7f0 \ub2e4\uc74c unsettled \ub178\ub4dc\uc9d1\ud569\uc5d0 \uc788\ub358 \ub178\ub4dc A\ub97c settled\ub178\ub4dc \uc9d1\ud569\uc73c\ub85c \uc774\ub3d9\uc2dc\uace0, \ub178\ub4dc B\uc640 C\ub97c unsettled\ub178\ub4dc\uc9d1\ud569\uc5d0 \ucd94\uac00\ud55c\ub2e4. \uc65c\ub0d0\ud558\uba74 \uc774 \ub450 \ub178\ub4dc\ub294 \ubc29\ubb38\ud560 \uc218\ub294 \uc788\uc9c0\ub9cc \uc544\uc9c1 \ud3c9\uac00\uac00 \ub418\uc9c0 \uc54a\uc558\uae30 \ub54c\ubb38\uc774\ub2e4.<\/p>\n\n\n\n
\ub450 \uac1c(B, C)\uc758 \ub178\ub4dc\uac00 unsettled\ub178\ub4dc\uc9d1\ud569\uc5d0 \ucd94\uac00\ub418\uc5c8\uc73c\ubbc0\ub85c \uc774\ub4e4 \uc911 \uac00\uc7a5 \uc9e7\uc740 \uac70\ub9ac\ub97c \uac16\ub294 \ub178\ub4dc(\uc774 \uacbd\uc6b0 \ub178\ub4dc B)\ub97c \uc120\ud0dd\ud55c\ub2e4. \uc774\ud6c4 \uadf8\ub798\ud504 \uc0c1\uc5d0 \uc874\uc7ac\ud558\ub294 \ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uc774 settled\uc9d1\ud569\uc73c\ub85c \uc774\ub3d9\ub420 \ub54c\uae4c\uc9c0 \uc774 \uc804\uccb4 \uacfc\uc815\uc744 \uacc4\uc18d \ubc18\ubcf5\ud55c\ub2e4.<\/p>\n\n\n\n![\"\"\/](\"https:\/\/www.baeldung.com\/wp-content\/uploads\/2017\/01\/step8.png\")
<\/figure>\n\n\n\n\ud3c9\uac00\ub2e8\uacc4\uc5d0\uc11c \uc218\ud589\ud558\ub294 \ubaa8\ub4e0 \ubc18\ubcf5 \uacfc\uc815\uc744 \uc815\ub9ac\ud558\uba74 \uc544\ub798 \ud45c\uc640 \uac19\ub2e4.<\/p>\n\n\n\n| Iteration<\/th> | Unsettled<\/th> | Settled<\/th> | EvaluationNode<\/th> | A<\/th> | B<\/th> | C<\/th> | D<\/th> | E<\/th> | F<\/th><\/tr> |
|---|
| 1<\/td> | A<\/td> | \u2013<\/td> | A<\/td> | 0<\/td> | A-10<\/strong><\/td>A-15<\/strong><\/td>| X-\u221e<\/td> | X-\u221e<\/td> | X-\u221e<\/td><\/tr> | | 2<\/td> | B, C<\/td> | A<\/td> | B<\/td> | 0<\/td> | A-10<\/td> | A-15<\/td> | B-22<\/strong><\/td>| X-\u221e<\/td> | B-25<\/strong><\/td><\/tr>| 3<\/td> | C, F, D<\/td> | A, B<\/td> | C<\/td> | 0<\/td> | A-10<\/td> | A-15<\/td> | B-22<\/td> | C-25<\/strong><\/td>| B-25<\/td><\/tr> | | 4<\/td> | D, E, F<\/td> | A, B, C<\/td> | D<\/td> | 0<\/td> | A-10<\/td> | A-15<\/td> | B-22<\/td> | D-24<\/strong><\/td>D-23<\/strong><\/td><\/tr>| 5<\/td> | E, F<\/td> | A, B, C, D<\/td> | F<\/td> | 0<\/td> | A-10<\/td> | A-15<\/td> | B-22<\/td> | D-24<\/td> | D-23<\/td><\/tr> | | 6<\/td> | E<\/td> | A, B, C, D, F<\/td> | E<\/td> | 0<\/td> | A-10<\/td> | A-15<\/td> | B-22<\/td> | D-24<\/td> | D-23<\/td><\/tr> | Final<\/strong><\/td>\u2013<\/strong><\/td>ALL<\/strong><\/td>NONE<\/strong><\/td>0<\/strong><\/td>A-10<\/strong><\/td>A-15<\/strong><\/td>B-22<\/strong><\/td>D-24<\/strong><\/td>| D-23<\/strong><\/td><\/tr><\/tbody><\/table>\ub2e8\uacc4\ubcc4 \ucd5c\ub2e8\uac70\ub9ac \uacc4\uc0b0<\/figcaption><\/figure>\n\n\n\n \uc704 \ud45c\uc5d0\uc11c \uc608\ub97c \ub4e4\uc5b4 B-22 \ud45c\ud604\uc740 \ub178\ub4dc B\uac00 \uc774\uc804 \ub178\ub4dc\uc774\uba70 \ucd9c\ubc1c\uc9c0 \ub178\ub4dc\uc778 \ub178\ub4dc A\ub85c\ubd80\ud130\uc758 \uac70\ub9ac\ub294 22\uc784\uc744 \ub098\ud0c0\ub0b8\ub2e4.<\/p>\n\n\n\n \ub9c8\uc9c0\ub9c9\uc73c\ub85c, \ub178\ub4dc A\ub85c\ubd80\ud130\uc758 \ucd5c\ub2e8\uac70\ub9ac \uacbd\ub85c\ub294 \uc544\ub798\uc640 \uac19\uc774 \uacc4\uc0b0\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n \n- Node B : A \u2013> B (total distance = 10)<\/li>\n\n\n\n
- Node C : A \u2013> C (total distance = 15)<\/li>\n\n\n\n
- Node D : A \u2013> B \u2013> D (total distance = 22)<\/li>\n\n\n\n
- Node E : A \u2013> B \u2013> D \u2013> E (total distance = 24)<\/li>\n\n\n\n
- Node F : A \u2013> B \u2013> D \u2013> F (total distance = 23)<\/li>\n<\/ul>\n\n\n\n
\uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h2>\n\n\n\n\uc55e\uc5d0\uc11c \uc124\uba85\ud55c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc758 \uac01 \ub2e8\uacc4\ub4e4\uc744 \ucef4\ud4e8\ud130 \uc5b8\uc5b4(Java Language)\ub85c \uad6c\ud604\ud574 \ubcf4\uc790. \uc2dc\uc791\ud558\uae30\uc5d0 \uc55e\uc11c \ub370\uc774\ud130 \ubaa8\ub378\uc5d0 \ud574\ub2f9\ud558\ub294 \uadf8\ub798\ud504\ub97c \uba3c\uc800 \ub9cc\ub4e4\uc5b4\uc57c \ud55c\ub2e4. \uadf8\ub798\ud504\ub294 \ub178\ub4dc\uc640 \ub178\ub4dc\ub4e4 \uc0ac\uc774\ub97c \uc5f0\uacb0\ud558\ub294 \ub9c1\ud06c\ub85c \uad6c\uc131\ub85c \ub41c\ub2e4. \ub178\ub4dc\uc640 \ub9c1\ud06c\ub9cc\uc73c\ub85c\ub3c4 \ucd5c\ub2e8\uacbd\ub85c \ucc3e\uae30 \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud560 \uc218 \uc788\uc9c0\ub9cc \uc5ec\uae30\uc11c\ub294 \uc880 \ub354 \ud604\uc2e4\uc801\uc73c\ub85c \uc811\uadfc\ud558\uae30 \uc704\ud574 \uc5f0\uacb0(Connection)\uc774\ub77c\ub294 \ucd94\uc0c1\uc801\uc778 \uac1c\ub150\uc744 \uac19\uc774 \uad6c\ud604\ud55c\ub2e4. Connection\uc740 \ub9c1\ud06c\uc640 \ub9c1\ud06c\ub97c \uc5f0\uacb0\ud55c \uac1c\ub150\uc73c\ub85c \ub0b4\ube44\uac8c\uc774\uc158\uc5d0\uc11c \uc88c\/\uc6b0\ud68c\uc804, xx\ubbf8\ud130 \uc55e \uc88c\/\uc6b0\ud68c\uc804 \uac19\uc774 \uae38\uc548\ub0b4\ub97c \ud560 \ub54c \ud544\uc694\ub85c \ud558\ub294 \uc815\ubcf4\ub4e4\uc744 \uad00\ub9ac\ud55c\ub2e4.<\/p>\n\n\n\n \ub178\ub4dc(Node)<\/h3>\n\n\n\n\ub178\ub4dc\ub294 \uadf8\ub798\ud504 \uc0c1\uc758 \uc815\uc810(Vertex)\ub97c \ub098\ud0c0\ub0b4\uba70 \ud604\uc2e4 \uc138\uacc4\uc758 \ud68c\ub2e8\ubcf4\ub3c4, \uad50\ucc28\ub85c \ub4f1 \ub3c4\ub85c\uac00 \ub17c\ub9ac\uc801\uc73c\ub85c \ub04a\uc5b4\uc9c0\ub294 \uc9c0\uc810\uc744 \ub178\ub4dc\ub85c \uc0dd\uac01\ud558\uba74 \uc774\ud574\uac00 \uc27d\ub2e4. \ub178\ub4dc \ud074\ub798\uc2a4\ub294 \ub178\ub4dc\uad00\ub828 \uc815\ubcf4\ub97c \uc800\uc7a5\ud558\ub294 Value Object\ub85c \ud65c\uc6a9\ub418\uba70 \ud2b9\uc774\ud55c \uc810\uc73c\ub85c\ub294 \ub9c1\ud06c \uc0dd\uc131\uc5d0 \ud65c\uc6a9\ub418\ub3c4\ub85d \ud558\uc600\ub2e4.<\/p>\n\n\n\n package app.dijkstra;\n\nimport java.util.Collection;\nimport java.util.HashMap;\nimport java.util.Map;\n\n\/**\n * Represents a Node object in a Graph. This class is used to conceptualize the road network topology in a Graph model.\n * This class is a simplified Node object so that, you can extend this class to apply this in a real world as you need.\n * @author skanto\n *\/\npublic class Node {\n private final String name;\n private final Map<Node, Link> links = new HashMap<>();\n \n \/**\n * Constructor. Creates new Node object with a node name. You can change name to a node id and context object\n * as a additional information parameter\n * @param name node name\n *\/\n public Node(String name) {\n this.name = name;\n }\n \n \/**\n * You can think of the Link as a connection between two links so that linking this Node object with the another\n * Node object returns new Link object. \n * @param to a node to which a Link object is created\n * @param length length information as a demonstration. You can extend length value to a additional\n * context information like the road level, lane count etc. \n * @return newly created Link object\n *\/\n public Link link(Node to, int length) {\n final Link link = new Link(this, to, length);\n links.put(to, link);\n return link;\n }\n \n \/**\n * Returns Link object associated with this Node object to the specified to Node. \n * @param to The other end of Link object \n * @return Link object that associated with the specified to Node.\n *\/\n public Link linked(Node to) {\n return links.get(to);\n }\n \n \/**\n * Returns all the Link objects associated with this Node object\n * @return All the Link objects as Collection\n *\/\n public Collection<Link> links() {\n return this.links.values();\n }\n \n \/**\n * Returns the naem of this Node object\n * @return name of this Node object\n *\/\n public String name() {\n return name;\n }\n \n @Override\n public String toString() {\n return name();\n }\n}<\/code><\/pre>\n\n\n\n\ub9c1\ud06c(Link)<\/h3>\n\n\n\n\ub178\ub4dc\uc640 \ub178\ub4dc\ub97c \uc5f0\uacb0\ud558\uba74 \ub9c1\ud06c\uac00 \uc0dd\uc131\ub418\uba70 \ud604\uc2e4 \uc138\uacc4\uc5d0\uc11c \ub3c4\ub85c\uc758 \ucd5c\uc18c \ub17c\ub9ac \ub2e8\uc704\ub85c \uc0dd\uac01\ud558\uba74 \uc774\ud574\uac00 \uc27d\ub2e4. \ub9c1\ud06c \ud074\ub798\uc2a4\ub3c4 Value Object\ub85c \ud65c\uc6a9\ub418\uba70 \ub178\ub4dc\ub97c \uc774\uc6a9\ud558\uc5ec \ub9c1\ud06c\ub97c \uc0dd\uc131\ud588\ub4ef\uc774 \ub9c1\ud06c\uc640 \ub9c1\ud06c\ub97c \uc5f0\uacb0\ud558\uc5ec Connection\uc744 \uc0dd\uc131\ud55c\ub2e4\ub294 \uac83\uc774 \ucc28\uc774\uc810\uc774\ub2e4.<\/p>\n\n\n\n package app.dijkstra;\n\nimport java.util.HashMap;\nimport java.util.Map;\n\n\/**\n * Represents Link object in a Graph. This class is used to conceptualize the road network topology(edge) in a Graph model.\n * This class is a simplified Link object so that, you can extend this class to apply this in a real world as you need.\n * @author skanto\n *\/\npublic class Link {\n private final Node from;\n private final Node to;\n private final int length;\n private final Map<Link, Connection> connections = new HashMap<>();\n \n \/**\n * Create new Link instance using the specified constructor parameters.\n * Notice: The constructor visibility is package scope so you can not instantiate Link object outside this package\n * @param from From side Node object of a Link\n * @param to To side Node object of a Link\n * @param length the length of the Link. You can extend this parameter to accommodate the real world situations \n *\/\n Link(Node from, Node to, int length) {\n this.from = from;\n this.to = to;\n this.length = length;\n }\n \n \/**\n * Returns From-side Node object of this Link object.\n * @return Node object\n *\/\n public Node from() {\n return from;\n }\n \n \/**\n * Returns To-side Node object of this Link object.\n * @return Node object\n *\/\n public Node to() {\n return to;\n }\n \n \/**\n * Returns the length of this Link \n * @return link length\n *\/\n public int length() {\n return length;\n }\n \n \/**\n * Connects this Link object with the specified link object that eventually creates a Connection instance.\n * @param outward Link object to connect with this Link object\n * @param angle angle value. You can extend this parameter to reflect real world situations.\n * @return Connection object\n *\/\n public Connection connect(Link outward, short angle) {\n connections.put(outward, new Connection(this, outward, angle));\n return connections.get(outward); \n }\n \n \/**\n * Finds Connection from this Link object which is connected with the specified outward Link object\n * @param outward Link object\n * @return Connection object\n *\/\n public Connection connected(Link outward) {\n return connections.get(outward);\n }\n \n @Override\n public String toString() {\n return String.format(\"[%s-%s: %s]\", from(), to(), length());\n }\n}<\/code><\/pre>\n\n\n\n\uc5f0\uacb0(Connection)<\/h3>\n\n\n\nConnection\uc740 \uc9c4\uc785(inward)\ub9c1\ud06c\uc640 \uc9c4\ucd9c(outward)\ub9c1\ud06c\ub85c \uad6c\uc131\ub418\uba70 \ub9c1\ud06c\uc640 \ub9c1\ud06c\uac00 \uc5f0\uacb0\ub418\uba74 \ud68c\uc804 \uac01\ub3c4\uc640 \uc9c4\uc785\uac00\ub2a5, \uc9c4\ucd9c\uac00\ub2a5 \ub4f1\uc758 \uc815\ubcf4\ub97c \uad00\ub9ac\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n package app.dijkstra;\n\n\/**\n * This class conceptualize the connection between two Link objects(inward, outward).\n * @author skanto\n *\/\npublic class Connection {\n private final Link inward;\n private final Link outward;\n private final short angle;\n \n \/**\n * Creates new Connection instance using the specified parameters. \n * Notice: The constructor visibility is package scope so you can not instantiate Connection object outside\n * this package\n * @param inward Inward Link object from the Connection. \n * @param outward Outward Link object from the Connection.\n * @param angle angle value. You can extend this parameter to reflect real world situations\n *\/\n Connection(Link inward, Link outward, short angle) {\n this.inward = inward;\n this.outward = outward;\n this.angle = angle;\n }\n \n \/**\n * Returns inward Link object from this Connection\n * @return Link object\n *\/\n public Link inward() {\n return this.inward;\n }\n \n \/**\n * Returns outward Link object from this Connection\n * @return Link object\n *\/\n public Link outward() {\n return this.outward;\n }\n \n \/**\n * Returns angle value of this Connection. This angle value is just for demonstration so you can extend this\n * property as a context to hold various information associated with the road connection. \n * @return angle value\n *\/\n public short getAngle() {\n return this.angle;\n }\n \n \/**\n *\n *\/\n public String toString() {\n return String.format(\"{%s->%s: %s}\", inward(), outward(), getAngle());\n }\n}<\/code><\/pre>\n\n\n\n\uac00\uc7a5 \ucd5c\uc18c\ud55c\uc73c\ub85c \uacbd\ub85c \ud0d0\uc0c9\uc5d0 \ud544\uc694\ud55c \uadf8\ub798\ud504 \ubaa8\ub378\uc774 \ub9cc\ub4e4\uc5b4 \uc84c\uc73c\ubbc0\ub85c \uc774\uc81c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud55c\ub2e4. \uc55e\uc5d0\uc11c \uc774\ub860\uc73c\ub85c \uc124\uba85\ud55c \ub0b4\uc6a9\uacfc \ub2e4\ub978 \uc810\uc740 \ucd9c\ubc1c\uc9c0\uc810 \ub178\ub4dc\ub85c\ubd80\ud130 \ucd5c\ub2e8\uac70\ub9ac\ub97c \uac01 \ub178\ub4dc\uc5d0 \uc800\uc7a5\ud558\uc9c0 \uc54a\uace0 \ubc29\ubb38(Visit)\uc774\ub77c\ub294 \uac1c\ub150\uc744 \ub3c4\uc785\ud558\uc5ec \uc5ec\uae30\uc5d0 \uc800\uc7a5\ub418\ub3c4\ub85d \ud558\uc600\uc73c\uba70 \ube44\uc6a9(Cost)\ub85c \ud45c\ud604\ud588\ub2e4. Visit\uac1d\uccb4\ub97c \uacbd\ub85c\ud0d0\uc0c9 \uacfc\uc815\uc5d0\uc11c \ud65c\uc6a9\ub418\ub294 \uc77c\ub828\uc758 \uc815\ubcf4\ub97c \uc800\uc7a5\ud558\ub294 Context \uac1d\uccb4\ub85c \uc0dd\uac01\ud574\ub3c4 \uc88b\ub2e4. \ube44\uc6a9\uc815\ubcf4\ub97c \ub370\uc774\ud130 \ubaa8\ub378\uc5d0 \uc800\uc7a5\ud560 \uacbd\uc6b0 \ubaa8\ub378\uc5d0 \uc885\uc18d\uc801\uc774 \ub418\uc5b4 \ud55c \uba85\uc758 \uc0ac\uc6a9\uc790\ub9cc \uc2e4\ud589\ud560 \uc218 \uc788\uac8c \ub41c\ub2e4. \ud558\uc9c0\ub9cc \uc2e4\uc81c \uc0c1\ud669\uc5d0\uc11c\ub294 \ud558\ub098\uc758 \ub370\uc774\ud130 \ubaa8\ub378\uc744 \uc774\uc6a9\ud558\uc5ec \ub2e4\uc218\uc758 \uc0ac\uc6a9\uc790\uac00 \uacbd\ub85c\ud0d0\uc0c9\uc744 \ucc98\ub9ac\ud558\ubbc0\ub85c \ub370\uc774\ud130 \ubaa8\ub378\uc5d0 \uc800\uc7a5\ud558\ub294 \uac83\uc774 \uc544\ub2c8\ub77c \uc0ac\uc6a9\uc790\ubcc4\ub85c(Thread) Context \uac1d\uccb4\ub97c \ub530\ub85c \uc720\uc9c0\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n \ubc29\ubb38(Visit)<\/h3>\n\n\n\npackage app.dijkstra;\n\nimport java.util.ArrayList;\nimport java.util.Collection;\nimport java.util.LinkedList;\nimport java.util.List;\n\n\/**\n * Encapsulates the context information that needs to maintain when traversing the graph to determine the optimal path. \n * @author skanto\n *\/\npublic class Visit {\n private final Node node;\n private Integer cost = Integer.MAX_VALUE; \/\/ set the cost to infinite value as a default\n private List<Node> shortcut = new LinkedList<Node>();\n \n \/**\n * Creates new Visit object with the specified Node object\n * @param node Node object\n *\/\n Visit(Node node) {\n this.node = node;\n }\n \n \/**\n * Returns the Node related to the current Visit\n * @return Node object\n *\/\n public Node node() {\n return this.node;\n }\n \n \/**\n * Returns the cost of current Visit that accumulated from the source. you can take many aspects of driving\n * scenarios into account as a cost not just link length alone.\n * @return cost value\n *\/\n public int cost() {\n return this.cost;\n }\n \n \/**\n * Returns the current shortest path accumulated so far from the source\n * @return shortest path as a List object\n *\/\n public List<Node> shortcut() {\n return this.shortcut;\n }\n \n \/**\n * Updates the shortcut and cost information with the specified shortcut and cost.\n * @param shortcut List object that has Node object as a list\n * @param cost cost to update. Usually the specified cost is lower than the cost of this object \n *\/\n public void update(List<Node> shortcut, int cost) {\n this.shortcut = shortcut;\n this.cost = cost;\n }\n \n \/**\n * Traces the connection from the source Node to this Visit Node and returns as a Collection object\n * The Collection object has connection information related to the optimal path\n * @return Collection object that contains Connections from the source to this Visit object\n *\/\n public Collection<Connection> trace() {\n List<Node> visits = new LinkedList<>(shortcut());\n visits.add(node());\n if (visits.size() < 3) throw new IllegalStateException(String.format(\"Can not make trajectory: %s\", visits));\n List<Connection> connections = new ArrayList<>();\n for (int from = 0, via = from + 1, to = via + 1; to < visits.size(); from++, via++, to++) {\n Link inward = visits.get(from).linked(visits.get(via));\n Link outward = visits.get(via).linked(visits.get(to));\n connections.add(inward.connected(outward));\n }\n return connections;\n }\n \n @Override\n public String toString() {\n return String.format(\"%s(%s)\", node(), cost());\n }\n}<\/code><\/pre>\n\n\n\n\ub2e4\uc775\uc2a4\ud2b8\ub77c(Dijkstra)<\/h3>\n\n\n\n\uc774\uc81c \ucd5c\ub2e8\uac70\ub9ac\ub97c \ucc3e\ub294 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud55c\ub2e4. Dijkstra \ud074\ub798\uc2a4\uc758 \ud575\uc2ec\uc740 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\ub294 \uacfc\uc815\uc73c\ub85c traverse \uba54\uc18c\ub4dc\uac00 \uc774 \uc804\uccb4 \uacfc\uc815\uc744 \uad6c\ud604\ud55c\ub2e4. \uc774 \uba54\uc18c\ub4dc\uc758 \ub3d9\uc791 \uacfc\uc815\uc744 \ubcf4\uba74 \uc55e\uc5d0\uc11c \uc124\uba85\ud55c \ub0b4\uc6a9\uc774 \uc774\ud574\ub420 \uac83\uc774\ub2e4.<\/p>\n\n\n\n package app.dijkstra;\n\nimport java.util.Comparator;\nimport java.util.HashSet;\nimport java.util.LinkedList;\nimport java.util.List;\nimport java.util.Optional;\nimport java.util.Set;\n\n\/**\n * This class implements Dijkstra Algorithm\n * @author skanto\n *\/\npublic class Dijkstra {\n \/**\n * Finds optimal path that has lowest cost form source to destination\n * @param source Node object that starts from\n * @param destination Node object that gets to\n * @return Visit object that has information for the optimal path.\n * If no visit exists between source and destination returns null\n *\/\n public static Visit traverse(Node source, Node destination) {\n Set<Visit> settled = new HashSet<>();\n Set<Visit> unsettled = new HashSet<>();\n\n Visit visit = new Visit(source);\n visit.update(visit.shortcut(), 0);\n unsettled.add(visit);\n \n while (unsettled.size() != 0) { \/\/ terminates when the all links are visited (no more unsettled element)\n \/* choose an adjacent visit that has minimum cost *\/\n visit = unsettled.stream().min(Comparator.comparing(Visit::cost)).get(); \n peek(unsettled, settled, visit); \/\/ prints snapshot of information\n unsettled.remove(visit);\n for (Link link: visit.node().links()) {\n Optional<Visit> any = unsettled.stream().filter(v -> v.node().equals(link.to())).findAny();\n \/\/ if exists reuse it otherwise creates new one\n Visit adjacent = any.isPresent() ? any.get() : new Visit(link.to());\n if (!settled.contains(adjacent)) { \n adjustShorcut(visit, adjacent, link);\n unsettled.add(adjacent);\n }\n }\n if (visit.node().equals(destination)) return visit; \/\/ the shortest path is found\n settled.add(visit);\n }\n return null;\n }\n \n \/**\n * Switches the cost of adjacent visit with the cost of the current visit if the cost of current visit is lower\n * than the adjacent visit as well as replaces the shortcut of adjacent with the current one.\n * @param current the context of current visit\n * @param adjacent the context of the adjacent Node visit \n * @param link the Link object from the current Visit node to the adjacent visit node\n *\/\n private static void adjustShorcut(Visit current, Visit adjacent, Link link) {\n if (adjacent.cost() <= current.cost() + link.length()) return; \/* no need to calculation *\/\n List<Node> shortcut = new LinkedList<>(current.shortcut()); \/\/ copy the current shortcut\n shortcut.add(current.node());\n adjacent.update(shortcut, current.cost() + link.length()); \/\/ updates the shortcut and cost simultaneously\n }\n\n \/**\n * Writes the information about current visit in the middle of Algorithm execution\n * @param unsettled Set containing Visits that has not been explored\n * @param settled Set containing Visits that has determined the lowest cost\n * @param evaluate Visit object the algorithm is now on \n *\/\n private static void peek(Set<Visit> unsettled, Set<Visit> settled, Visit evaluate) {\n System.out.printf(\"unsettled: %s\\nsettled: %s\\nevaluate: %s\\nprobe: %s\\n\\n\",\n unsettled, settled, evaluate, evaluate.node().links());\n }\n}<\/code><\/pre>\n\n\n\n\uc54c\uace0\ub9ac\uc998 \ud14c\uc2a4\ud2b8(Demo)<\/h3>\n\n\n\n\uc774\uc81c \uadf8\ub798\ud504 \ubaa8\ub378\uacfc \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud588\uc73c\ubbc0\ub85c \ucd5c\ub2e8\uac70\ub9ac\uac00 \uc815\uc0c1\uc801\uc73c\ub85c \uc0dd\uc131\ub418\ub294\uc9c0 \ud655\uc778\uc744 \uc704\ud574 \uc2e4\uc81c \ub370\uc774\ud130\ub97c \uc774\uc6a9\ud558\uc5ec \ub370\uc774\ud130 \ubaa8\ub378\uc744 \uc0dd\uc131\ud558\uace0 \uacbd\ub85c\ucc3e\uae30\ub97c \uc218\ud589\ud558\ub294 \uac04\ub2e8\ud55c \ub370\ubaa8 \ud504\ub85c\uadf8\ub7a8\uc744 \uc81c\uc791\ud55c\ub2e4.<\/p>\n\n\n\n package app.dijkstra;\n\n\/**\n * Demonstrates the working of Dijkstra algorithm\n * @author skanto\n *\/\npublic class Demo {\n \/**\n * C -- F\n * \/ \\ \/ \\\n * B -- D -- E -- G\n * \/ \/\n * -> A ------- C\n *\/\n public static void pathfinding() {\n Node A = new Node(\"A\");\n Node B = new Node(\"B\");\n Node C = new Node(\"C\");\n Node D = new Node(\"D\");\n Node E = new Node(\"E\");\n Node F = new Node(\"F\");\n Node G = new Node(\"G\");\n \n Link AB = A.link(B, 10);\n Link BD = B.link(D, 12);\n Link BF = B.link(F, 15);\n AB.connect(BD, (short) 110);\n AB.connect(BF, (short) 160);\n \n Link AC = A.link(C, 15);\n Link CE = C.link(E, 10);\n AC.connect(CE, (short) 130);\n\n Link DE = D.link(E, 2);\n BD.connect(DE, (short) 140);\n \n Link DF = D.link(F, 1);\n BD.connect(DF, (short) 80);\n \n Link FE = F.link(E, 5);\n BF.connect(FE, (short) 200);\n DF.connect(FE, (short) 90);\n \n Link EG = E.link(G, 8);\n FE.connect(EG, (short) 170);\n DE.connect(EG, (short) 180);\n CE.connect(EG, (short) 80);\n \n Node source = A, destination = G;\n Visit visit = Dijkstra.traverse(source, destination);\n System.out.printf(\"Shortcut to %s: %s, Cost: %s\\n\", destination, visit.shortcut(), visit.cost());\n System.out.printf(\"Route: %s\\n\", visit.trace());\n }\n \n \/**\n * @param args\n *\/\n public static void main(String[] args) { pathfinding(); }\n}<\/code><\/pre>\n\n\n\n\uc704 Demo \ud504\ub85c\uadf8\ub7a8\uc744 \uc2e4\ud589\ud558\uba74 \uc544\ub798\uc640 \uac19\uc774 \ucd9c\ubc1c\uc9c0 \ub178\ub4dc(A)\uc640 \ubaa9\uc801\uc9c0 \ub178\ub4dc(G)\uc0ac\uc774\uc5d0 \ucd5c\ub2e8\uac70\ub9ac\uac00 \uc0dd\uc131\ub418\ub294 \uac83\uc744 \ud655\uc778\ud560 \uc218 \uc788\ub2e4. \ubaa9\uc801\uc9c0 \ub178\ub4dc\uae4c\uc9c0\uc758 \ucd5c\ub2e8\uac70\ub9ac\uc758 \ub178\ub4dc\ub294 A->B->D->E \uc774\uba70 Cost\ub294 32\uac00 \ub41c\ub2e4. \uc774\ub54c \uacbd\ub85c \uc5f0\uacb0(Connection)\uc740 {[A-B:]->[B-D]}, {[B-D]->[D-E]}, {[D-E]->[E-G]}]\uac00 \ub428\uc744 \ud655\uc778\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n unsettled: [A(0)]\nsettled: []\nevaluate: A(0)\nprobe: [[A-C: 15], [A-B: 10]]\n\nunsettled: [C(15), B(10)]\nsettled: [A(0)]\nevaluate: B(10)\nprobe: [[B-F: 15], [B-D: 12]]\n\nunsettled: [D(22), F(25), C(15)]\nsettled: [A(0), B(10)]\nevaluate: C(15)\nprobe: [[C-E: 10]]\n\nunsettled: [D(22), F(25), E(25)]\nsettled: [C(15), A(0), B(10)]\nevaluate: D(22)\nprobe: [[D-F: 1], [D-E: 2]]\n\nunsettled: [F(23), E(24)]\nsettled: [D(22), C(15), A(0), B(10)]\nevaluate: F(23)\nprobe: [[F-E: 5]]\n\nunsettled: [E(24)]\nsettled: [D(22), F(23), C(15), A(0), B(10)]\nevaluate: E(24)\nprobe: [[E-G: 8]]\n\nunsettled: [G(32)]\nsettled: [D(22), F(23), C(15), A(0), B(10), E(24)]\nevaluate: G(32)\nprobe: []\n\nShortcut to G: [A, B, D, E], Cost: 32\nRoute: [{[A-B: 10]->[B-D: 12]: 110}, {[B-D: 12]->[D-E: 2]: 140}, {[D-E: 2]->[E-G: 8]: 180}]<\/code><\/pre>\n\n\n\n\ub9c8\uce58\uba70…<\/h2>\n\n\n\n\uc774 \uae00\uc5d0\uc11c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc774 \uc5b4\ub5bb\uac8c \ucd5c\ub2e8\uac70\ub9ac\ub97c \ucc3e\uc544\ub0b4\ub294\uc9c0 \uc54c\uc544 \ubcf4\uc558\ub2e4. \uc2e4\uc81c \ub0b4\ube44\uac8c\uc774\uc158\uc758 \uacbd\ub85c\ud0d0\uc0c9\uc740 \uc704\uc5d0\uc11c \uc124\uba85\ud55c \uae30\ubcf8 \uae30\ub2a5 \uc678\uc5d0 \ub2e4\uc591\ud55c \uace0\ub824\uc0ac\ud56d\uc774 \ubc18\uc601\ub418\uc9c0\ub9cc \uae38\ucc3e\uae30\uc5d0\uc11c \ud575\uc2ec\uc801\uc73c\ub85c \uc801\uc6a9\ub418\ub294 \ub3d9\uc791\uc740 \ub3d9\uc77c\ud558\ub2e4\uace0 \ubcf4\uba74 \ub41c\ub2e4.<\/p>\n","protected":false},"excerpt":{"rendered":" \uac1c\uc694 \uc774 \uae00\uc740 \uc790\ub3d9\ucc28 \ub0b4\ube44\uac8c\uc774\uc158\uc758 \uacbd\ub85c\ud0d0\uc0c9 \ub610\ub294 \uadf8\ub798\ud504 \uc774\ub860\uc5d0\uc11c \uc811\ud558\ub294 \ucd5c\ub2e8\uac70\ub9ac \ud0d0\uc0c9\uc5d0 \ub300\ud574 \uc124\uba85\ud55c\ub2e4. \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \ucd5c\ub2e8\uac70\ub9ac \uacbd\ub85c\ud0d0\uc0c9\uc5d0 \ud65c\uc6a9\ub418\ub294 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c\ub294 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc774 \ub300\ud45c\uc801\uc774\ub77c \ud560 \uc218 \uc788\ub2e4. \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc774 \ub0b4\ubd80\uc801\uc73c\ub85c \uc5b4\ub5a4 \ucc98\ub9ac\uacfc\uc815\uc744 \uac70\uccd0 \uacb0\uacfc\ub97c \ub9cc\ub4e4\uc5b4\ub0b4\ub294\uc9c0\uc5d0 \ub300\ud574 \uc0b4\ud3b4\ubcf4\ub3c4\ub85d \ud55c\ub2e4. \ub2e4\uc775\uc2a4\ud2b8\ub77c\ub97c \uc774\uc6a9\ud55c \ucd5c\ub2e8\uac70\ub9ac \ucc3e\uae30 \uadf8\ub798\ud504 \uc774\ub860\uc5d0\uc11c \uadf8\ub798\ud504\ub294 \ub9c1\ud06c(edge)\uc640 \ub178\ub4dc(vertex)\ub85c \uad6c\uc131\ub41c\ub2e4. \ub9c1\ud06c\uc5d0 \uac00\uc911\uce58(weight)\uac00 \uc801\uc6a9\ub418\ub294 \uadf8\ub798\ud504\ub97c \uac00\uc911\uce58 \uadf8\ub798\ud504(weighted graph)\ub77c\uace0 \ud558\uba70 \uc774 \uac00\uc911\uce58 \uadf8\ub798\ud504 \uc0c1\uc5d0\uc11c \ucd9c\ubc1c\uc9c0 \ub178\ub4dc\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc740 \uc774 \ucd9c\ubc1c\uc9c0 \ub178\ub4dc\uc640 \uc5f0\uacb0 \uac00\ub2a5\ud55c \ubaa8\ub4e0 \ubaa9\uc801\uc9c0 \ub178\ub4dc\ub4e4 \uc0ac\uc774\uc758 \ucd5c\ub2e8\uac70\ub9ac \uacbd\ub85c\uc640 \uac70\ub9ac(\uac00\uc911\uce58\uc758 \ud569)\ub97c \uad6c\ud574\ub0b8\ub2e4….<\/p>\n Read More 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],"tags":[114,112,113],"class_list":["post-1205","post","type-post","status-publish","format-standard","hentry","category-sw-development","tag-dijkstra","tag-112","tag-113"],"_links":{"self":[{"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/1205","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=1205"}],"version-history":[{"count":6,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/1205\/revisions"}],"predecessor-version":[{"id":1216,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/1205\/revisions\/1216"}],"wp:attachment":[{"href":"https:\/\/skanto.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1205"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1205"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1205"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
| | | | | | | | | | | | | | | | |
![\"\"\/](\"https:\/\/www.baeldung.com\/wp-content\/uploads\/2017\/01\/initial-graph.png\")
<\/figure>\n\n\n\n![\"\"\/](\"https:\/\/www.baeldung.com\/wp-content\/uploads\/2017\/01\/step1.png\")
<\/figure>\n\n\n\n