\n \ucf54\ub529 \ud14c\uc2a4\ud2b8\ub294 \ud604\ub300\uc758 \uae30\uc220 \uc9c1\uad70\uc5d0\uc11c \ud544\uc218\uc801\uc778 \ub2a5\ub825\uc744 \ud3c9\uac00\ud558\ub294 \uc911\uc694\ud55c \ub2e8\uacc4\uc785\ub2c8\ub2e4. \ud2b9\ud788 \uadf8\ub798\ud504 \uc774\ub860\uc740 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c \ud754\ud788 \uc694\uad6c\ub418\ub294 \uc8fc\uc81c\uc774\uba70, \uadf8\uc911\uc5d0\uc11c\ub3c4 \ubca8\ub9cc-\ud3ec\ub4dc \uc54c\uace0\ub9ac\uc998\uc740 \ub2e8\uc77c \ucd9c\ubc1c\uc810\uc5d0\uc11c \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370 \ub110\ub9ac \uc0ac\uc6a9\ub429\ub2c8\ub2e4. \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 \ucf54\ud2c0\ub9b0\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubca8\ub9cc-\ud3ec\ub4dc \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud558\uace0, \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc790\uc138\ud788 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n \ubca8\ub9cc-\ud3ec\ub4dc \uc54c\uace0\ub9ac\uc998\uc740 \uc8fc\uc5b4\uc9c4 \uadf8\ub798\ud504\uc5d0\uc11c \ud558\ub098\uc758 \uc815\uc810\uc5d0\uc11c \ub2e4\ub978 \ubaa8\ub4e0 \uc815\uc810\uc73c\ub85c\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ud2b9\ud788 \uc74c\uc758 \uac00\uc911\uce58\ub97c \uac00\uc9c4 \uac04\uc120\uc774 \uc874\uc7ac\ud560 \ub54c \uc720\uc6a9\ud569\ub2c8\ub2e4. \ubca8\ub9cc-\ud3ec\ub4dc \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4:\n <\/p>\n
\n \ub2e4\uc74c\uacfc \uac19\uc740 \uadf8\ub798\ud504\uac00 \uc788\ub2e4. \uc815\uc810\uacfc \uac04\uc120\uc740 \uc544\ub798\uc640 \uac19\uc774 \uc8fc\uc5b4\uc84c\ub2e4. \uac01 \uac04\uc120\uc758 \uac00\uc911\uce58\ub294 \ud45c\uc2dc\ub418\uc5b4 \uc788\ub2e4.\n <\/p>\n
\n \uc815\uc810:\n 0, 1, 2, 3, 4\n\n \uac04\uc120:\n 0 -> 1 (4)\n 0 -> 2 (1)\n 1 -> 2 (2)\n 1 -> 3 (5)\n 2 -> 3 (8)\n 3 -> 4 (3)\n 2 -> 4 (7)\n <\/pre>\n\n 0\ubc88 \uc815\uc810\uc5d0\uc11c \ub2e4\ub978 \ubaa8\ub4e0 \uc815\uc810\uc73c\ub85c\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uacc4\uc0b0\ud558\ub77c.\n <\/p>\n
4. \ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
4.1 \uc785\ub825 \ub370\uc774\ud130 \uc124\uacc4<\/h3>\n
\n \uba3c\uc800, \uc704\uc758 \uadf8\ub798\ud504\ub97c \ucf54\ub4dc\ub85c \ud45c\ud604\ud558\uae30 \uc704\ud574, \uc815\uc810\uacfc \uac04\uc120\uc744 \ub370\uc774\ud130 \uad6c\uc870\ub85c \uc815\uc758\ud574\uc57c \ud569\ub2c8\ub2e4. \ucf54\ud2c0\ub9b0\uc5d0\uc11c\ub294 \ub9ac\uc2a4\ud2b8\uc640 \ub370\uc774\ud130 \ud074\ub798\uc2a4\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc27d\uac8c \uad6c\ud604\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n
4.2 \ucf54\ud2c0\ub9b0 \ub370\uc774\ud130 \ud074\ub798\uc2a4 \uc815\uc758<\/h3>\n
\n data class Edge(val u: Int, val v: Int, val weight: Int)\n <\/pre>\n4.3 \ubca8\ub9cc-\ud3ec\ub4dc \uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h3>\n
\n fun bellmanFord(edges: List, vertexCount: Int, startVertex: Int): IntArray {\n val distance = IntArray(vertexCount) { Int.MAX_VALUE }\n distance[startVertex] = 0\n\n for (i in 1 until vertexCount) {\n for (edge in edges) {\n if (distance[edge.u] != Int.MAX_VALUE && distance[edge.u] + edge.weight < distance[edge.v]) {\n distance[edge.v] = distance[edge.u] + edge.weight\n }\n }\n }\n\n \/\/ \uc74c\uc758 \uac00\uc911\uce58 \uc0ac\uc774\ud074 \uac80\uc99d\n for (edge in edges) {\n if (distance[edge.u] != Int.MAX_VALUE && distance[edge.u] + edge.weight < distance[edge.v]) {\n throw IllegalArgumentException(\"\uc74c\uc758 \uac00\uc911\uce58 \uc0ac\uc774\ud074 \uc874\uc7ac\")\n }\n }\n\n return distance\n }\n <\/edge><\/pre>\n 5. \uc804\uccb4 \uad6c\ud604<\/h2>\n
\n fun main() {\n val edges = listOf(\n Edge(0, 1, 4),\n Edge(0, 2, 1),\n Edge(1, 2, 2),\n Edge(1, 3, 5),\n Edge(2, 3, 8),\n Edge(3, 4, 3),\n Edge(2, 4, 7)\n )\n \n val result = bellmanFord(edges, 5, 0)\n println(\"0\ubc88 \uc815\uc810\uc5d0\uc11c \ub2e4\ub978 \uc815\uc810\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uac70\ub9ac: ${result.joinToString(\", \")}\")\n }\n <\/pre>\n6. \ucd9c\ub825 \uacb0\uacfc<\/h2>\n
\n \uc704 \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uba74 0\ubc88 \uc815\uc810\uc5d0\uc11c \ub2e4\ub978 \ubaa8\ub4e0 \uc815\uc810\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uac70\ub9ac\ub97c \uc54c \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uae30\ub300\ud558\ub294 \uacb0\uacfc\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:\n <\/p>\n
\n 0\ubc88 \uc815\uc810\uc5d0\uc11c \ub2e4\ub978 \uc815\uc810\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uac70\ub9ac: 0, 3, 1, 11, 10\n <\/pre>\n7. \uacb0\ub860<\/h2>\n
\n \ubca8\ub9cc-\ud3ec\ub4dc \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ucd5c\ub2e8 \uacbd\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ub2e8\uc21c\ud558\uba74\uc11c\ub3c4 \uac15\ub825\ud55c \uae30\ub2a5\uc744 \uc81c\uacf5\ud569\ub2c8\ub2e4. \ud2b9\ud788 \uc74c\uc758 \uac00\uc911\uce58\uac00 \uc788\uc744 \ub54c \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ub420 \uc218 \uc788\uc74c\uc744 \uac15\uc870\ud558\uace0 \uc2f6\uc2b5\ub2c8\ub2e4. \ucf54\ud2c0\ub9b0\uc744 \uc774\uc6a9\ud574 \uad6c\ud604\ud574\ubcf4\uba74\uc11c, \uc54c\uace0\ub9ac\uc998\uc758 \uc791\ub3d9 \ubc29\uc2dd\uc744 \ub354\uc6b1 \uc798 \uc774\ud574\ud560 \uc218 \uc788\uc5c8\uc744 \uac83\uc785\ub2c8\ub2e4. \ucf54\ub529 \ud14c\uc2a4\ud2b8\ub97c \uc900\ube44\ud558\uba70 \ubca8\ub9cc-\ud3ec\ub4dc \uc54c\uace0\ub9ac\uc998\uc744 \uc2e4\uc2b5\ud574\ubcf4\uc138\uc694!\n <\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"