{"id":1256,"date":"2024-05-01T10:25:22","date_gmt":"2024-05-01T01:25:22","guid":{"rendered":"https:\/\/skanto.co.kr\/?p=1256"},"modified":"2024-05-20T09:33:14","modified_gmt":"2024-05-20T00:33:14","slug":"understanding-bidirectional-dijkstra-algorithm","status":"publish","type":"post","link":"https:\/\/skanto.co.kr\/?p=1256","title":{"rendered":"Understanding Bidirectional Dijkstra Algorithm"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Dijkstra Algorithm\uc740 \ub0b4\ube44\uac8c\uc774\uc158\uc758 \uae38\ucc3e\uae30 \ubfd0\ub9cc \uc544\ub2c8\ub77c \ucd5c\ub2e8\uac70\ub9ac\ub97c \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \uc798 \uc54c\ub824\uc838 \uc788\ub2e4. Dijkstra Algorithm\uc740 \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \ucd5c\ub2e8 \uac70\ub9ac \ud0d0\uc0c9\uc744 \ubcf4\uc7a5\ud558\uae34 \ud558\uc9c0\ub9cc \ud0d0\uc0c9 \uac70\ub9ac\uac00 \uba40\uba74 \uba40\uc218\ub85d \uc18c\uc694\ub418\ub294 \uc2dc\uac04\ub3c4 \ube44\ub840\uc801\uc73c\ub85c \uc99d\uac00\ud55c\ub2e4\ub294 \uac83\uc774 \ub9f9\uc810\uc774\ub2e4. \uc774\ub7f0 \ubb38\uc81c\uc810\uc744 \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub2e4\uc591\ud55c \ubc29\ubc95\ub4e4\uc774 \uc2dc\ub3c4 \ub418\uc5c8\uc73c\uba70 \uadf8 \uc911 \ub300\ud45c\uc801\uc778 \uac83\uc774 A*\uc640 \uc591\ubc29\ud5a5 \ud0d0\uc0c9\uc774\ub77c \ud560 \uc218 \uc788\ub2e4. \uc774 \uae00\uc5d0\uc11c\ub294 \ub0b4\ube44\uac8c\uc774\uc158 \uc5c5\uacc4\uc5d0\uc11c \uc8fc\ub85c \uc801\uc6a9\ud558\uace0 A*\uc54c\uace0\ub9ac\uc998\ubcf4\ub2e4 \ucd5c\uc801 \uacbd\ub85c \ud0d0\uc0c9\uc744 \ubcf4\uc7a5\ud558\uba74\uc11c \ud0d0\uc0c9\uc2dc\uac04\uc744 \uac70\uc758 \uc808\ubc18\uc73c\ub85c \uc904\uc77c \uc218 \uc788\ub294 \uc591\ubc29\ud5a5 \ud0d0\uc0c9(Bidirectional Dijkstra Algorithm)\uc744 \uc790\uc138\ud788 \uc54c\uc544\ubcf4\uace0\uc790 \ud55c\ub2e4. \ucc38\uace0\ub85c Dijkstra Algorithm\uc5d0 \ub300\ud574 \uc774\ud574\uac00 \ud544\uc694\ud558\ub2e4\uba74 <a href=\"https:\/\/skanto.co.kr\/?p=1205\" data-type=\"post\" data-id=\"1205\">\uc774\uc804 \uae00<\/a>\uc744 \ucc38\uace0\ud558\uae30 \ubc14\ub780\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Introduction<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub984\uc5d0\uc11c \uc720\ucd94\ud560 \uc218 \uc788\ub4ef\uc774 Bidirectional Dijkstra\ub294 \uc591\ubc29\ud5a5 \uc989, \ucd9c\ubc1c\uc9c0\uc5d0\uc11c \uc815\ubc29\ud5a5\uc73c\ub85c, \ubaa9\uc801\uc9c0\uc5d0\uc11c\ub294 \uc5ed\ubc29\ud5a5\uc73c\ub85c \ub3d9\uc2dc\uc5d0 \ud0d0\uc0c9\ud574 \ub098\uac00\ub2e4\uac00 \uc11c\ub85c \ub9cc\ub098\ub294 \uc9c0\uc810\uc5d0\uc11c \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc774\ub2e4. \uc5b8\ub73b \ubcf4\uae30\uc5d0\ub294 \ub2e4\uc18c \ubcf5\uc7a1\ud574 \ubcf4\uc77c \uc218\ub3c4 \uc788\uc9c0\ub9cc \ud070 \uadf8\ub9bc\uc744 \uc774\ud574\ud558\uace0 \ub098\uba74 \uc0ac\uc2e4 \ub2e8\uc21c\ud55c \uc54c\uace0\ub9ac\uc998\uc774\ub77c \ub290\ub07c\uac8c \ub420 \uac83\uc774\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub178\ub4dc V(vertex)\uc640 \ub9c1\ud06c E(edge)\ub97c \uac00\uc9c4 \uadf8\ub798\ud504 G\uc640 \ubaa8\ub4e0 \ub9c1\ud06c\uc758 \ubc29\ud5a5\uc131\uc744 \ub4a4\uc9d1\uc740 \uadf8\ub798\ud504 G&#8217;\uac00 \uc788\ub2e4\uace0 \ud558\uc790 . \uc5ec\uae30\uc11c \uadf8\ub798\ud504G\uc0c1\uc5d0 \uc788\ub294 \ucd9c\ubc1c\uc9c0 \ub178\ub4dc\uc640 \uadf8\ub798\ud504G&#8217;\uc5d0 \uc788\ub294 \ubaa9\uc801\uc9c0 \ub178\ub4dc\uc5d0\uc11c \uc11c\ub85c \ub3d9\uc2dc\uc5d0 \ud0d0\uc0c9\uc744 \uc2dc\uc791\ud574 \ub098\uac04 \ud6c4 \ub450 \ud0d0\uc0c9\uacf5\uac04(Search Space)\uac00 \uc11c\ub85c \ub9cc\ub0a0 \ub54c\uae4c\uc9c0 \uc774\uc5b4\uac04\ub2e4. \uc774\uc640 \uac19\uc740 \ubc29\uc2dd\uc73c\ub85c \uc9c4\ud589\ud574 \ub098\uac00\uba74 \ud0d0\uc0c9\uacf5\uac04\uc758 \ud06c\uae30\ub294 \ub2e8\ubc29\ud5a5 \ud0d0\uc0c9\ubcf4\ub2e4 \uac70\uc758 1\/2\uc218\uc900\uc73c\ub85c \uc904\uc5b4\ub4e0\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Algorithm<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Dijkstra \uc54c\uace0\ub9ac\uc998\uacfc \uac19\uc774 \uadf8\ub798\ud504 G\uc5d0 \uc788\ub294 \ucd9c\ubc1c\uc9c0 \ub178\ub4dc s\uc640 \uadf8\ub798\ud504 G&#8217;\uc5d0 \uc788\ub294 \ubaa9\uc801\uc9c0 \ub178\ub4dc t\uc5d0\uc11c \ud0d0\uc0c9\uc744 \uc2dc\uc791\ud55c\ub2e4.<\/li>\n\n\n\n<li>\ud0d0\uc0c9\uacfc\uc815\uc5d0\uc11c \ubc29\ubb38\ud558\ub294 \ub178\ub4dc\ub294 \uc815\ubc29\ud5a5\uc77c\uacbd\uc6b0 \ucd9c\ubc1c\uc9c0(s)\uc5d0\uc11c\ubd80\ud130, \uc5ed\ubc29\ud5a5\uc77c\uacbd\uc6b0 \ubaa9\uc801\uc9c0(t)\ub85c\ubd80\ud130\uc758 \ucd5c\ub2e8\uac70\ub9ac(distance)\ub97c \uc800\uc7a5\ud558\ub3c4\ub85d \ud558\uace0 \ucd08\uae30\uac12\uc740 \ubb34\ud55c\ub300(\u221e)\ub85c \uc124\uc815\ud55c\ub2e4.<\/li>\n\n\n\n<li>\uc815\ubc29\ud5a5\uacfc \uc5ed\ubc29\ud5a5 \ud0d0\uc0c9\uc5d0\uc11c \ucd5c\ub2e8\uac70\ub9ac \ub178\ub4dc\uc758 \uc2dd\ubcc4\uc744 \uc704\ud574 \uc0ac\uc6a9\ud560 PriorityQueue(Qf, Qb)\ub97c \uac01\uac01 \uc720\uc9c0\ud55c\ub2e4.<\/li>\n\n\n\n<li>\uc815\ubc29\ud5a5,\uc5ed\ubc29\ud5a5 \ud0d0\uc0c9\uc774 \uc11c\ub85c \ub9cc\ub0a0 \uacbd\uc6b0 \ub450 \ud0d0\uc0c9 \uacf5\uac04\uc5d0 \uacf5\ud1b5\uc73c\ub85c \uc874\uc7ac\ud558\ub294 \ub178\ub4dc\ub97c \uc800\uc7a5\ud558\uae30 \uc704\ud55c Join Node(\uc811\uc810\ub178\ub4dc)\ub97c \uc900\ube44\ud55c\ub2e4.<\/li>\n\n\n\n<li>\ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \ucd5c\ub2e8\uac70\ub9ac\ub85c \ucd94\uc815\ub418\ub294 \uac12\uc744 \uc800\uc7a5\ud558\uae30 \uc704\ud55c \u03bc\ub97c \uc900\ube44\ud558\uace0 \ucd08\uae30\uac12\uc744 \ubb34\ud55c\ub300\ub85c \uc124\uc815\ud55c\ub2e4.<\/li>\n\n\n\n<li>\uc815\ubc29\ud5a5, \uc5ed\ubc29\ud5a5\uc744 \uc11c\ub85c \ubc88\uac08\uc544 \uac00\uba70 Dijkstra \ud0d0\uc0c9\uc744 \uc9c4\ud589\ud55c\ub2e4.<\/li>\n\n\n\n<li>PriorityQueue\uc5d0\uc11c \ucd94\ucd9c\ub41c \ub178\ub4dc\ub97c x, \uc774 \ub178\ub4dc\uc640 \uc778\uc811\ud558\uace0 \uc788\ub294 \ub178\ub4dc\ub97c y\ub77c\uace0 \ud560 \ub54c \ucd9c\ubc1c\uc9c0(s)\uc5d0\uc11c x\uae4c\uc9c0\uc758 \ucd5c\ub2e8\uac70\ub9ac\uc640 \ubaa9\uc801\uc9c0(t)\uc5d0\uc11c y\uae4c\uc9c0\uc758 \ucd5c\ub2e8\uac70\ub9ac, \uadf8\ub9ac\uace0 x, y\ub97c \ub178\ub4dc\ub85c \uac16\ub294 \ub9c1\ud06c\uc758 \uae38\uc774\ub97c \ubaa8\ub450 \ub354\ud55c \uac12\uc744 \uad6c\ud558\uace0 \uc774 \uac12\uc774 \u03bc\ubcf4\ub2e4 \uc791\uc744 \uacbd\uc6b0 \uc791\uc740 \uac12\uc73c\ub85c \u03bc\ub97c \uc5c5\ub370\uc774\ud2b8\ud574 \ub098\uac04\ub2e4. \uc774\ub54c y\ub178\ub4dc\ub97c Join Node\ub85c \uc800\uc7a5\ud574 \ub454\ub2e4.<br><em>: if DistanceF(x) + Length of Link(x, y) + DistanceB(y) &lt; \u03bc<\/em><\/li>\n\n\n\n<li>Qf\uc5d0\uc11c \ucd94\ucd9c\ud55c \ub178\ub4dc\uc758 \ucd5c\ub2e8\uac70\ub9ac\uc640 Qb\uc5d0\uc11c \ucd94\ucd9c\ud55c \ub178\ub4dc\uc758 \ucd5c\ub2e8\uac70\ub9ac \ud569\uc774 \u03bc\ubcf4\ub2e4 \ud06c\uac70\ub098 \uac19\uc744 \uacbd\uc6b0 \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud55c\ub2e4.<br><em>: if Qf.top.distance + Qb.top.distance &gt;= \u03bc<\/em><\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">\uc704 \uc54c\uace0\ub9ac\uc998 \uc124\uba85\uc5d0\uc11c \ub450 \uac00\uc9c0 \uacbd\uc6b0\ub294 \uc880 \ub354 \uae4a\uc740 \uc774\ud574\uac00 \ud544\uc694\ud558\uba70 \uc544\ub798 \uadf8\ub9bc\uc73c\ub85c \uc124\uba85\uc774 \uac00\ub2a5\ud558\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc6b0\uc120 \uc591\ubc29\ud5a5 \ud0d0\uc0c9\uc774 \uc11c\ub85c \ub9cc\ub098\uba74 \ud0d0\uc0c9\uc744 \uc911\ub2e8\ud558\uba70 \uc774\ub54c \ub9cc\ub09c \ub178\ub4dc\ub97c \uc5f0\uacb0\ud558\ub294 \uacbd\ub85c\uac00 \ucd5c\ub2e8\uacbd\ub85c\ub77c\uace0 \uc0dd\uac01\ud560 \uc218 \uc788\uc73c\ub098 \ud56d\uc0c1 \uadf8\ub7f0 \uac83\uc740 \uc544\ub2c8\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\/bidirectional\/counter-1.png\" alt=\"\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc815\/\uc5ed \ud0d0\uc0c9 \ub2e8\uacc4\uc5d0\uc11c \ub450 PriorityQueue\uc5d0\uc11c \ucd5c\uc18c\uac12 \ub178\ub4dc\ub97c \ud558\ub098\uc529 \uaebc\ub0b4 \ucc98\ub9ac\ud55c\ub2e4\uace0 \ud558\uba74 \uc5ed\ubc29\ud5a5 \ud0d0\uc0c9\uc5d0\uc11c \uadf8\ub9bc \ud558\ub2e8 \ub178\ub4dc\uac00 \uba3c\uc800 \ucc98\ub9ac\ub418\uace0 \uc0c1\ub2e8\uc758 \ub178\ub780\uc0c9 \ub178\ub4dc\uac00 \uc5ed\uc2dc \uc5ed\ubc29\ud5a5 \ud0d0\uc0c9\uc5d0\uc11c \ucc98\ub9ac\ub41c\ub2e4. \uadf8\ub7f0 \ub2e4\uc74c \uc815\ubc29\ud5a5 \ud0d0\uc0c9\uc5d0\uc11c \uc0c1\ub2e8\uc758 \ub178\ub780\uc0c9 \ub178\ub4dc\uac00 \ucc98\ub9ac\ub418\ub294 \uacfc\uc815\uc73c\ub85c \uc9c4\ud589\ub41c\ub2e4. \uc774\ub54c \ub3d9\uc77c\ud55c \ub178\ub4dc(\uc0c1\ub2e8 \ub178\ub780\uc0c9 \ub178\ub4dc)\uac00 \uc815\/\uc5ed\ubc29\ud5a5 \ud0d0\uc0c9\uc5d0\uc11c \uac01\uac01 \ucc98\ub9ac\ub418\uc5c8\ub2e4\uace0 \ud574\uc11c \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud574\ubc84\ub9ac\uba74 \uc2e4\uc81c \ucd5c\ub2e8\uacbd\ub85c\uc778 \ubd84\ud64d\uc0c9 \uacbd\ub85c\ub294 \uc120\ud0dd\ub418\uc9c0 \uc54a\ub294 \ubb38\uc81c\uac00 \ubc1c\uc0dd\ud55c\ub2e4. \ub530\ub77c\uc11c \uc2e4\uc81c \ucd5c\ub2e8 \uacbd\ub85c\ub294 \uc544\ub798\uc640 \uac19\uc774 \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\"><em>\uc591\ubc29\ud5a5 \ud0d0\uc0c9\uacfc\uc815\uc5d0\uc11c \ub3c4\ub2ec\ud558\ub294 \ubaa8\ub4e0 \ub178\ub4dc u \uc5d0 \ub300\ud574, dist(s, t) = <strong>min{dist(s, u) + dist(t, u)}<\/strong><\/em><\/p>\n<\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub294 \ucd9c\ubc1c\uc9c0\/\ubaa9\uc801\uc9c0\uc5d0\uc11c \uc2dc\uc791\ud558\ub294 \uc591\ubc29\ud5a5 \ud0d0\uc0c9\uacf5\uac04\uc5d0 \uacf5\ub3d9\uc73c\ub85c \uc874\uc7ac\ud558\ub294 \ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uc5d0 \ub300\ud574 \uae30\uc810\uc73c\ub85c\ubd80\ud130 \uac01\uac01\uc758 \ucd5c\ub2e8\uac70\ub9ac\uc758 \ud569\uc774 \ucd5c\uc18c\uac00 \ub418\ub294 \uacbd\ub85c\uac00 \uc2e4\uc81c \ucd5c\ub2e8\uacbd\ub85c\uac00 \ub41c\ub2e4\ub294 \uc758\ubbf8\uc774\uba70 \uc704 \uadf8\ub9bc\uc5d0\uc11c \ubcf4\uba74 \ubd84\ud64d\uc0c9 \uacbd\ub85c\uac00(19&lt;20) \ucd5c\ub2e8\uacbd\ub85c\uac00 \ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub97c \uc880 \ub354 \uc815\ud615\ud654 \ub41c \uac80\uc99d \ubc29\uc2dd\uc73c\ub85c \uc124\uba85\ud558\uc790\uba74 \uc544\ub798\uc640 \uac19\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Proof of Correctness<\/h2>\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\/bidirectional\/proof-1.png\" alt=\"\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\ucd9c\ubc1c\uc9c0 \ub178\ub4dc(s)\uc640 \ubaa9\uc801\uc9c0 \ub178\ub4dc(t), \uadf8\ub9ac\uace0 p, q, r \ub178\ub4dc\ub97c \uac16\ub294 \uc704\uc640 \uac19\uc740 \uadf8\ub798\ud504\ub97c \uc0dd\uac01\ud574 \ubcf4\uc790. s\uc640 t\uc0ac\uc774 \ucd5c\ub2e8\uacbd\ub85c\uc758 \uae38\uc774\ub97c D\ub77c \ud558\uace0 \ucc98\uc74c\uc73c\ub85c \uc591\ubc29\ud5a5\uc5d0\uc11c \uac01\uac01 \ucc98\ub9ac(settled)\ub418\ub294 \ub178\ub4dc\ub97c p\ub77c\uace0 \ud560 \uacbd\uc6b0 <em>dist(s, p) = dist(t, p) = D\/2<\/em> \uc774\uba74 p\ub294 s\uc640 t\uc0ac\uc774 \ucd5c\ub2e8\uacbd\ub85c \uc0c1\uc5d0 \uc874\uc7ac\ud558\ubbc0\ub85c \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud558\uba74 \ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uadf8\ub807\uc9c0\ub9cc \uc704 \uadf8\ub9bc\uc740 <em>dist(s, p)<\/em>\uc640 <em>dist(t, p)<\/em>\uac00 <em>D\/2<\/em>\uc640 \uac19\uc9c0 \uc54a\uc744 \uacbd\uc6b0\ub3c4 \uac19\uc774 \ubcf4\uc5ec\uc900\ub2e4. \uc774 \uacbd\uc6b0\ub294 <em>dist(s, p)<\/em>, <em>dist(t, p)<\/em>\uac00 \ubaa8\ub450 <em>D\/2<\/em>\ubcf4\ub2e4 \uc791\uc744 \uc218\ubc16\uc5d0 \uc5c6\ub294 \uc0c1\ud669\uc774\uace0 \uc774\ub294 \uc55e\uc11c p\uc758 \uacbd\uc6b0\ub97c \uc0dd\uac01\ud574\ubcf4\uba74 <em>D\/2<\/em>\ubcf4\ub2e4 \uc791\uc740 \ucd5c\ub2e8\uac70\ub9ac\ub97c \uac16\ub294 \ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uc740 \uc774\ubbf8 \uc591\ubc29\ud5a5\uc5d0\uc11c \ucc98\ub9ac(settled)\ub418\uc5b4\ubc84\ub838\uc74c\uc744 \uc758\ubbf8\ud55c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">s\uc640 t\uc0ac\uc774\uc758 \ucd5c\ub2e8\uacbd\ub85c \uc0c1\uc5d0 \ub178\ub4dc q, r\uc774 \uc788\uace0 <em>dist(s, q) &lt;= D\/2<\/em> \uc774\uace0 <em>dist(t, r) &lt;= D\/2<\/em>\uc77c \uacbd\uc6b0 q\ub294 s\ub97c \uae30\uc810\uc73c\ub85c r\uc740 t\ub97c \uae30\uc810\uc73c\ub85c \ucc98\ub9ac\ub41c \uc0c1\ud0dc\uac00 \ub41c\ub2e4. \uc774\ud6c4 \ub9c1\ud06c qr\ub3c4 \uc591 \ubc29\ud5a5\uc5d0\uc11c relax\ub41c \uc0c1\ud0dc\uc774\ubbc0\ub85c q\uc640 r\ub178\ub4dc\ub294 \uacb0\uc815\ub41c \ucd5c\ub2e8\uac70\ub9ac\ub97c \uac00\uc9c0\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uacb0\uad6d \ub178\ub4dc s, t\uc0ac\uc774 \ucd5c\ub2e8\uacbd\ub85c\uc758 \uae38\uc774\ub294 <em>dist(s, q) + dist(t, q)<\/em> \uc640 <em>dist(s, r) + dist(t, r)<\/em>\ubcf4\ub2e4 \uc791\uc744 \uc218 \ubc16\uc5d0 \uc5c6\uc74c\uc744 \uc758\ubbf8\ud55c\ub2e4. (\uc774 \uacbd\uc6b0\ub294 <em>dist(s, q) + dist(t, q)<\/em>, <em>dist(s, r) + dist(t, r)<\/em>\ub294 \ub3d9\uc77c\ud55c \uac12\uc744 \uac00\uc9d0)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub530\ub77c\uc11c, \ub178\ub4dc\uac00 \ub450 \ubc88 \ucc98\ub9ac(settled)\ub41c\ub2e4\uace0 \ud574\uc11c \uadf8 \ub178\ub4dc\uac00 \ubc18\ub4dc\uc2dc \ucd5c\ub2e8\uacbd\ub85c\uc0c1\uc5d0 \uc788\ub2e4\uace0 \ubcf4\uc7a5\ud560 \uc218 \uc5c6\uc9c0\ub9cc \ud0d0\uc0c9 \uc885\ub8cc \uc804\uae4c\uc9c0 \uc801\uc5b4\ub3c4 \ucd9c\ubc1c\uc9c0(s)\uc640 \ubaa9\uc801\uc9c0(t)\ub85c\ubd80\ud130\uc758 \uac70\ub9ac\uac00 \uacb0\uc815\ub41c \ub178\ub4dc 1\uac1c\ub294 \ucd5c\ub2e8\uacbd\ub85c\uc0c1\uc5d0 \uc874\uc7ac\ud558\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\uc81c \uc544\ub798\uc758 \uadf8\ub9bc\uc744 \uc774\uc6a9\ud574\uc11c \uc54c\uace0\ub9ac\uc998\uc758 \ub0b4\uc6a9\uc744 \uc774\ud574\ud574 \ubcf4\ub3c4\ub85d \ud558\uc790.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Explanations step by step<\/h2>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" src=\"https:\/\/miro.medium.com\/v2\/resize:fit:4800\/format:webp\/1*4ia06SONUmsbw3nfz9U0AQ.png\" alt=\"\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc774 \uadf8\ub9bc\uc5d0\uc11c \ubcfc \uc218 \uc788\ub4ef\uc774 \ucd9c\ubc1c\uc9c0 a\uc5d0\uc11c \uc2dc\uc791\ud574\uc11c \ubaa9\uc801\uc9c0 e\ub85c \uac00\ub294 \ucd5c\ub2e8\uacbd\ub85c\ub294 [a, h, g, f ,e] \uc774\uace0 \uc774\ub54c \uac70\ub9ac\ub294 21\uc774\ub2e4.  \uc774\uc81c  Bidirectional Dijkstra Algorithm\uc744 \uc2e4\ud589\ud558\uc5ec \ub3d9\uc77c\ud55c \ucd9c\ubc1c\uc9c0, \ubaa9\uc801\uc9c0\ub97c \ub300\uc0c1\uc73c\ub85c \ucd5c\ub2e8\uacbd\ub85c\ub97c \ucc3e\uc544\ubcf4\uc790.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\uac01 \uadf8\ub798\ud504 \ud558\ub2e8\uc5d0 \uc788\ub294 \ud45c\ub294 \uc815\ubc29\ud5a5 \ud0d0\uc0c9(F)\uc5d0\uc11c \ucd9c\ubc1c\uc9c0 \ub178\ub4dc\ub85c \ubd80\ud130\uc758 \ucd5c\ub2e8\uac70\ub9ac\uc640 \uc5ed\ubc29\ud5a5 \ud0d0\uc0c9(B)\uc5d0\uc11c \ubaa9\uc801\uc9c0 \ub178\ub4dc\ub85c \ubd80\ud130\uc758 \ucd5c\ub2e8\uac70\ub9ac\ub97c \ub098\ud0c0\ub0b8\ub2e4.<\/li>\n\n\n\n<li>QF, QB\ub294 \uc815\/\uc5ed\ubc29\ud5a5 \ud0d0\uc0c9\uc5d0\uc11c \uac01\uac01 \uc0ac\uc6a9\ub418\ub294 PriorityQueue\uc774\uba70 \uc774\ub4e4 PriorityQueue\ub294 <strong>[\uac70\ub9ac, \ub178\ub4dc]<\/strong>\ub85c \ud45c\uc2dc\ub418\uba70 \uc67c\ucabd \uc55e\ucabd \ubc29\ud5a5\uc774 \ucd5c\ub2e8\uac70\ub9ac\ub97c \uac16\ub294 \ub178\ub4dc\ub97c \ub098\ud0c0\ub0b8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, QF\uc758 [4, b]\ub294 \ucd9c\ubc1c\uc9c0 \ub178\ub4dc a\ub85c\ubd80\ud130 \ub178\ub4dc b\uae4c\uc9c0\uc758 \uac70\ub9ac\ub294 4\uac00 \ub428\uc744 \ub098\ud0c0\ub0b8\ub2e4.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/miro.medium.com\/v2\/resize:fit:720\/format:webp\/1*bi9pQiayjKH4DBYb7yt7QQ.png\" alt=\"\" style=\"width:820px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\uc774\uc81c \uac01 \ub2e8\uacc4\ubcc4\ub85c \uc54c\uace0\ub9ac\uc998\uc744 \uc774\ud574\ud574 \ubcf4\uc790.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>1\ub2e8\uacc4, \ucd9c\ubc1c\uc9c0, \ubaa9\uc801\uc9c0 \ub178\ub4dc\ub97c \uc815\/\uc5ed\ubc29\ud5a5 PriorityQueue\uc5d0 \ucd94\uac00\ud55c\ub2e4.<\/li>\n\n\n\n<li>2\ub2e8\uacc4, QB\uc5d0\uc11c \ucd5c\uc18c\uac12 \ub178\ub4dc\ub97c poll\ud558\uace0(\uc774 \uacbd\uc6b0 e) Queue\uc5d0 d\uc640 f\ub97c \ucd94\uac00\ud55c\ub2e4.<\/li>\n\n\n\n<li>3\ub2e8\uacc4, QF\ub294 \ucd5c\ub2e8\uac70\ub9ac\uc778 [0, a]\ub97c \uac00\uc9c0\uace0 \uc788\uc73c\ubbc0\ub85c \uc774 \uac12\uc744 poll\ud558\uace0 b\uc640 h\ub97c Queue\uc5d0 \ucd94\uac00\ud55c\ub2e4.<\/li>\n\n\n\n<li>4\ub2e8\uacc4, QF\uac00 [4, b]\ub85c \ub2e4\uc2dc \ucd5c\ub2e8\uac70\ub9ac\ub97c \uac00\uc9c0\ubbc0\ub85c \uc774 \uac12\uc744 poll\ud55c \ub2e4\uc74c c\ub97c Queue\uc5d0 \ucd94\uac00\ud55c\ub2e4.<\/li>\n\n\n\n<li>5\ub2e8\uacc4, QF\uac00 \ub2e4\uc2dc [8, h]\ub85c \ucd5c\ub2e8\uac70\ub9ac\ub97c \uac00\uc9c0\ubbc0\ub85c \uc774 \uac12\uc744 poll\ud55c \ud6c4 g\uc640 i\ub97c Queue\uc5d0 \ucd94\uac00\ud55c\ub2e4.<\/li>\n\n\n\n<li>6\ub2e8\uacc4, \uc774\uc81c QF\uc640 QB\uac00 \ub3d9\uc77c\ud55c \uac70\ub9ac \uac12\uc744 \uac00\uc9c0\ubbc0\ub85c QB\uc5d0\uc11c [9, d]\ub97c poll\ud55c\ub2e4. \uc774\uc81c \ucc98\uc74c\uc73c\ub85c Join Node c\ub97c \ub9cc\ub0ac\uc73c\uba70 \uc774\ub54c \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \uacbd\ub85c\ub294 [a, b, c, d, e]\uc774\uba70  \uac70\ub9ac <em>\u03bc<\/em>=28\uc774 \ub41c\ub2e4. \uadf8\ub7ec\ub098, \uc774\ub294 \ucd5c\ub2e8\uacbd\ub85c\uac00 \ub418\uc9c0 \ubabb\ud55c\ub2e4.<\/li>\n\n\n\n<li>7\ub2e8\uacc4, \ucd5c\ub2e8\uac70\ub9ac\ub294 QF\uc5d0 \uc788\ub294 [9, g]\uc774\uba70 \uc774 \uac12\uc744poll\ud55c\ub2e4. \uc774\uc81c \ub450 \ubc88\uc9f8\ub85c \uac70\ub9ac <em>\u03bc<\/em>=21\uc778 Join Node f\ub97c \ub9cc\ub09c\ub2e4. \uc774 \uac12\uc740 \uc55e\uc11c 28\ubcf4\ub2e4 \uc791\uc73c\ubbc0\ub85c \ucd5c\ub2e8\uacbd\ub85c\ub294 [a, h, g, f, e]\uc774\uba70 \uac70\ub9ac\ub294 21\uc774 \ub41c\ub2e4.<\/li>\n\n\n\n<li><em><strong>QF.top.distance + QB.top.distance &gt;= \u03bc<\/strong><\/em> \uc778\uc9c0 \uccb4\ud06c\ud558\uba70 12 + 10 &gt;= 21\uc774 \ub418\ubbc0\ub85c \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud55c\ub2e4.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\uc640 \uac19\uc774 Bidirectional Dijkstra Algorithm\uc744 \uc774\uc6a9\ud558\uc5ec \uac70\ub9ac\uac00 21\uc778 [a, h, g, f, e]\uc758 \ucd5c\ub2e8\uacbd\ub85c \ud0d0\uc0c9 \uacfc\uc815\uc744 \uc0b4\ud3b4 \ubcf4\uc558\ub2e4. \uc704 \uacfc\uc815\uc744 pseudo\ucf54\ub4dc\ub85c \uc62e\uae30\uba74 \uc544\ub798\uc640 \uac19\ub2e4.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>while Qf is not empty and Qb is not empty:\n    u = extract_min(Qf); v = extract_min(Qb)\n    Sf.add(u); Sb.add(v)\n    for x in adj(u):\n        relax(u, x)\n        if x in Sb and df&#91;u] + w(u, x) + db&#91;x] &lt; mu:\n            mu = df&#91;u] + w(u, x) + db&#91;x]\n    for x in adj(v):\n        relax(v, x)\n        if x in Sf and db&#91;v] + w(v, x) + df&#91;x] &lt; mu:\n            mu = db&#91;v] + w(v, x) + df&#91;x]\n    if df&#91;u] + db&#91;v] &gt;= mu:\n        break # mu is the true distance s-t<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\uc591\ubc29\ud5a5\uc758 PriorityQueue(Qf, Qb)\uac00 \uacf5\ubc31\uc774 \ub420 \ub54c\uae4c\uc9c0 \uc815\/\uc5ed\ubc29\ud5a5\uc5d0\uc11c \ud0d0\uc0c9\uc744 \uc9c4\ud589\ud558\uba70 frontier\ub178\ub4dc(x)\uac00 \ubc18\ub300\ud3b8 \ud0d0\uc0c9\uacf5\uac04\uc5d0 \uc874\uc7ac\ud560 \uacbd\uc6b0 \ucd9c\ubc1c\uc9c0\/\ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \uacbd\ub85c\uc758 \uac70\ub9ac \u03bc\ub97c \uacc4\uc0b0\ud558\uace0 \uc774 \uac12\uc774 \ucd5c\uc18c\uac00 \ub418\ub3c4\ub85d \uc5c5\ub370\uc774\ud2b8\ud574 \ub098\uac04\ub2e4. \uc989,  PriorityQueue\uc5d0 \ud3ec\ud568\ub418\ub294 frontier\ub178\ub4dc\ub97c \uc774\uc6a9\ud558\uc5ec \uc7a0\uc815\uc801\uc73c\ub85c \ub9cc\ub4e4\uc5b4\uc9c0\ub294 \uacbd\ub85c\uc758 \uae38\uc774\uac00 \ucd5c\ub2e8\uac70\ub9ac\uac00 \ub418\uba74 \ucd5c\ub2e8\uac70\ub9ac \uacbd\ub85c\uac00 \ub418\uace0 \uc774\ub54c frontier\ub178\ub4dc x\uac00 \uc591\ubc29\ud5a5\uc5d0\uc11c\uc758 Join Node\uac00 \ub41c\ub2e4. \uc704 \ucf54\ub4dc \ub9c8\uc9c0\ub9c9 \ubd80\ubd84\uacfc \uac19\uc774 \ucd9c\ubc1c\uc9c0(s)\/\ub3c4\ucc29\uc9c0(t) \ub178\ub4dc\ub85c\ubd80\ud130 \uc815\/\uc5ed\ubc29\ud5a5\uc5d0\uc11c \ucc98\ub9ac\ub41c(settled, <em>Sf.add(u); Sb.add(v)<\/em>)\ub178\ub4dc u, v\uc758 \ucd5c\ub2e8\uac70\ub9ac \ud569(<em>df[u] + db[v]<\/em>)\uc774 \u03bc\ubcf4\ub2e4 \ud06c\uac70\ub098 \uac19\uc544\uc9c0\uba74 \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud55c\ub2e4. \ub610\ud55c \uc704 \ucf54\ub4dc\uc5d0\ub294 \ud45c\ud604\uc774 \ub418\uc9c0 \uc54a\uc558\uc9c0\ub9cc \ucd5c\uc801\uc758 \uacb0\uacfc(best result)\ub97c \ub3c4\ucd9c\ud558\uae30 \uc704\ud574 \uc815\ubc29\ud5a5\/\uc5ed\ubc29\ud5a5\uc758 \ud0d0\uc0c9\uacf5\uac04\uc758 \ud06c\uae30\ub97c \uc11c\ub85c \ub9de\ucd94\ub294 \uac83\ub3c4 \uc911\uc694\ud558\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ud0d0\uc0c9 \uc885\ub8cc \ud6c4 \uc811\uc810\ub178\ub4dc\uc778 Join Node\ub97c \uae30\uc900\uc73c\ub85c \uc815\ubc29\ud5a5 \ud0d0\uc0c9\uc5d0\uc11c \ub9cc\ub4e4\uc5b4\uc9c4 \uacbd\ub85c\uc640 \uc5ed\ubc29\ud5a5\uc5d0\uc11c \ub9cc\ub4e4\uc5b4\uc9c4 \uacbd\ub85c\ub97c \uc11c\ub85c \uc5f0\uacb0\ud558\uba74 \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \ucd5c\ub2e8\uacbd\ub85c\uac00 \ub9cc\ub4e4\uc5b4 \uc9c4\ub2e4. \uc774 \ub54c \uc8fc\uc758\ud560 \uc810\uc740 \uc5ed\ubc29\ud5a5\uc5d0\uc11c \ub9cc\ub4e4\uc5b4\uc9c4 \uacbd\ub85c\ub294 \ubaa8\ub4e0 \ub9c1\ud06c\uc758 \uc21c\uc11c\ub97c \ub4a4\uc9d1\uc5b4\uc11c \uc5f0\uacb0\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Implementation<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\uc9c0\uae08\uae4c\uc9c0\uc758 \ub0b4\uc6a9\uc744 Java\ucf54\ub4dc\ub85c \uc62e\uae30\uba74 \uc544\ub798\uc640 \uac19\uc740 \ud615\ud0dc\uac00 \ub41c\ub2e4. \uac1c\ubc1c\uc790\ub9c8\ub2e4 \uad6c\ud604 \ubc29\ubc95\uc774 \ub2e4\ub97c \uc218 \uc788\uc73c\ub2c8 \ucc38\uace0\ub85c \uc0dd\uac01\ud574 \uc8fc\uae30 \ubc14\ub780\ub2e4. \ucf54\ub4dc\ub97c \ubcf4\uba74 \uc704\uc5d0\uc11c \uc124\uba85\ud55c \uac1c\ub150\ub4e4\uc774 \uc5b4\ub5bb\uac8c \uc801\uc6a9\ub418\uc5c8\ub294\uc9c0 \ub300\uccb4\uc801\uc73c\ub85c \uc774\ud574\ub97c \ud560 \uc218 \uc788\uc744 \uac83\uc73c\ub85c \uc608\uc0c1\ub418\uc5b4 \uad6c\uccb4\uc801\uc778 \ucf54\ub4dc \uc124\uba85\uc740 \uc0dd\ub7b5\ud558\uae30\ub85c \ud55c\ub2e4.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/**\n * BidirectionalDijkstra.java\n *\/\npackage march.alg;\n\nimport java.time.Duration;\nimport java.time.Instant;\nimport java.util.Collection;\nimport java.util.HashMap;\nimport java.util.HashSet;\nimport java.util.Map;\nimport java.util.Optional;\nimport java.util.Set;\n\nimport march.graph.Graph.Dir;\nimport march.graph.Link;\nimport march.graph.Node;\n\n\/**\n * BidirectionalDijkstra algorithm implementation class.\n * The overall implementation logic came from the following article linked. \n * @see &lt;a href=\"https:\/\/www.homepages.ucl.ac.uk\/~ucahmto\/math\/2020\/05\/30\/bidirectional-dijkstra.html\">Bidirectional Dijkstra&lt;\/a>\n * @see &lt;a href=\"https:\/\/www.cs.princeton.edu\/courses\/archive\/spr06\/cos423\/Handouts\/EPP%20shortest%20path%20algorithms.pdf\">Efficient Point-to-Point Shortest Path Algorithms&lt;\/a>\n * @author skanto\n *\/\npublic class BidirectionalDijkstra implements Traveller {\n    \n    \/**\n     * Thread local variable to save Metric information of this Algorithm\n     *\/\n    private final static ThreadLocal&lt;Metric> threadLocal = new ThreadLocal&lt;>();\n\n    \/**\n     * returns the name of this class as a algorithm name\n     *\/\n    public String name() {\n        return this.getClass().getSimpleName();\n    }\n\n    \/**\n     * Finds an optimal path from the given source and destination node that the total cost of every node is minimal.\n     * @param source a source {@link Node} object.\n     * @param destination a destination {@link Node} object.\n     * @return a Route object that contains information of shortest path\n     * @throws IllegalArgumentException If no path is found between source and destination\n     *\/\n    public final Route traverse(Node source, Node destination) {\n        final SearchSpace ss = new SearchSpace(1000);\n        final MutableQueue&lt;Node, Visit> Qf = new MutablePriorityQueue&lt;>(700), Qb = new MutablePriorityQueue&lt;>(700);\n        final Instant start = Instant.now(); \/\/ to measure the time elapsed\n        Visit vf = new Visit(source, Dir.F)\/* forward *\/, vb = new Visit(destination, Dir.B); \/* backward *\/\n        vf.replace(null, 0, 0); vb.replace(null, 0, 0); \/\/ set initial values\n        Qf.offer(vf); Qb.offer(vb);\n        \/* explores forward and backward direction in the order as defined, processes the same workload *\/\n        while (!Qf.isEmpty() &amp;&amp; !Qb.isEmpty() &amp;&amp; !ss.satisfied(vf.cost() + vb.cost()) \/* break condition *\/ ) {\n            vf = explore(Qf, ss) \/* explore forward *\/;\n            vb = explore(Qb, ss) \/* explore backward*\/;\n        }\n        measure(start, Qf, Qb, ss); \/\/ gathers metric information\n        \/\/ if mutual() is true then the two search spaces have met each other at any node in the intersection area\n        if (ss.mutual()) return ss.route(); \/\/ merges each route from both search spaces\n        throw new IllegalArgumentException(String.format(\"Path from %s to %s does not exist\", source, destination));\n    }\n\n    \/**\n     * Do the actual processing of Dijkstra algorithm using the specified parameter information. This method can be\n     * utilized to search road networks forward and backward according to the type of Queue specified as a parameter\n     * @param queue PriorityQueue object it can be either forward or backward PriorityQueue\n     * @param ss SearchSpace object which holds forward and backward search space information\n     * @return Visit object explored\n     *\/\n    private final Visit explore(MutableQueue&lt;Node, Visit> queue, SearchSpace ss) {\n        final Visit visit = queue.poll();\n        for (Node frontier: visit.frontiers()) {\n            Visit adjacent = queue.pick(frontier).orElseGet(() -> visit.reach(frontier));\n            if (ss.contains(adjacent)) continue; \/\/ if the adjacent node is settled already\n            if (relax(visit, adjacent)) {\n                if (queue.has(frontier)) queue.mutate(adjacent); else queue.offer(adjacent);\n            }\n            \/\/ vo - opposite Visit object\n            ss.get(adjacent, adjacent.dir().flip()).ifPresent(vo -> ss.update(mu(visit, vo),  adjacent));\n        }\n        ss.settle(visit);\n        return visit;\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 visit the context of current visit\n     * @param adjacent the context of the adjacent Node visit \n     * @return {@code true} if the cost of adjacent Visit is updated otherwise returns false \n     *\/\n    protected boolean relax(Visit visit, Visit adjacent) {\n        \/* cost that consumes by passing through the specified link *\/\n        final Link passage = visit.passage(adjacent);\n        final float cost = visit.cost() + expense(passage); \/\/link.elapse();\n        if (adjacent.cost() &lt;= cost) return false; \/* no need to calculate hereafter *\/\n        adjacent.replace(visit, visit.ETA() + passage.elapse(), cost); \/\/ updates previous &amp; cost simultaneously\n        return true;\n    }\n\n    \/**\n     * Calculates the mu(\u03bc) value using the specified parameters. vf is a Visit object which is in the forward\n     * search space and vb is a Visit object which is in the backward search space. Each vf and vb has the distance from\n     * the source and destination respectively. mu is calculated as follows:\n     * &lt;ol>\n     *   &lt;li>calculate the distance from the source to the vf Visit node&lt;\/li>\n     *   &lt;li>calculate the distance from the destination to the vb Visit node&lt;\/li>\n     *   &lt;li>calculate the distance of link from the node of vf to the node of vb&lt;\/li>\n     *   &lt;li>sums up all distances above\n     * &lt;\/ol> \n     * @param vf a Visit object in the forward search space\n     * @param vb a Visit object in the backward search space\n     * @return calculated value: mu(\u03bc) value (tentative shortest distance from the source to destination)\n     *\/\n    private final float mu(Visit vf, Visit vb) {\n        return vf.cost() + expense(vf.passage(vb)) + vb.cost();\n    }\n    \n    \/**\n     * Returns the cost of the specified link object\n     * You can extend the functionality of this method if you want by applying like real time speed or road type etc.\n     * @param link Link object\n     * @return the cost of the specified link object\n     *\/\n    private final float expense(Link link) {\n        return link.metadata.length;\n    }\n    \n    \/**\n     * Measure the status of this algorithm. This method saves all the nodes the algorithm has visited,\n     * the time it took and the count the algorithm will visit afterward in thread local variable.\n     * @param start the time the algorithm starts\n     * @param Qf PriorityQueue used in forward searching\n     * @param Qb PriorityQueue used in backward searching\n     * @param ss SearchSpae object(holds all the settled Visit objects)\n     *\/\n    @SuppressWarnings(\"serial\")\n    private void measure(Instant start, final MutableQueue&lt;Node, Visit> Qf, final MutableQueue&lt;Node, Visit> Qb,\n            final SearchSpace ss) {\n        final float elapsed = (float) Duration.between(start, Instant.now()).toMillis()\/1000;\n        final Set&lt;Node> frontiers = new HashSet&lt;Node>() {{ addAll(Qf.keys()); addAll(Qb.keys()); }};\n        threadLocal.set(new Metric() { \/\/ saves metric information in the thread local variable\n            public Collection&lt;? extends Route> visited() { return ss.visited(); }\n            public Collection&lt;Node> frontiers() { return frontiers; } \n            public float elapsed() { return elapsed; }\n        });\n    }\n    \n    @Override\n    public Metric metric() {\n        Metric metric = threadLocal.get();\n        threadLocal.remove();\n        return metric;\n    }\n    \n    \/**\n     * This class conceptualize Search Space used in Bidirectional Dijkstra Algorithm. It holds forward search space\n     * and backward search space respectively and implements convenient methods.\n     * @author skanto\n     *\/\n    private class SearchSpace {\n        private float mu = Float.MAX_VALUE; \/\/ the length(distance) from the source to the destination\n        private final Map&lt;Node, Visit> sf; \/\/ Forward Search Space\n        private final Map&lt;Node, Visit> sb; \/\/ Backward Search Space\n        private Node node = null;\n        \n        \/**\n         * Constructor \n         * @param initial initial search space size\n         *\/\n        SearchSpace(int initial) {\n            sf = new HashMap&lt;>(initial);\n            sb = new HashMap&lt;>(initial);\n        }\n        \n        \/**\n         * Returns search space denoted by the direction\n         * @param dir direction (Forward\/Backward)\n         * @return search space\n         *\/\n        private final Map&lt;Node, Visit> space(Dir dir) {\n            return Dir.F.equals(dir) ? sf : sb;\n        }\n        \n        \/**\n         * settles the specified Visit object in the search space denoted by the direction\n         * @param visit a Visit object to settle\n         * @param dir direction(Forward\/Backward)\n         *\/\n        void settle(Visit visit) {\n            space(visit.dir()).put(visit.node(), visit);\n        }\n        \n        \/**\n         * Checks if the specified Visit object is contained in this search space according to the direction of\n         * the visit\n         * @param visit visit object\n         * @return return true if the specified visit is contained in this search space\n         *\/\n        boolean contains(Visit visit) {\n            return contains(visit, visit.dir());\n        }\n        \n        \/**\n         * Checks if the specified Visit object is contained in this search space denoted by the direction of\n         * the visit\n         * @param visit visit object\n         * @param dir search direction(Forward\/Backward)\n         * @return returns true if a search space denoted by the direction contains the node object associated\n         *  with the specified visit object otherwise returns false\n         *\/\n        boolean contains(Visit visit, Dir dir) {\n            return contains(visit.node(), dir);\n        }\n        \n        \/**\n         * Checks if the specified node object exists in the search space denoted by the direction\n         * @param node a Visit node to check\n         * @param dir direction(Forward\/Backward)\n         * @return return true if current search space contains the specified Visit object otherwise returns false \n         *\/\n        boolean contains(Node node, Dir dir) {\n            return space(dir).containsKey(node);\n        }\n        \n        \/**\n         * Finds a Visit object using the specified visit object and direction\n         * @param visit a Visit object whose node acts as a key to the target Visit object\n         * @param dir direction(Forward\/Backward)\n         * @return returns a Visit object if exists otherwise returns null\n         *\/\n        Optional&lt;Visit> get(Visit visit, Dir dir) {\n            return Optional.ofNullable(space(dir).get(visit.node()));\n        }\n        \n        \/**\n         * Finds and returns all the Node objects search space in forward and backward holds \n         * @return all the Node object as a Collection\n         *\/\n        @SuppressWarnings(\"serial\")\n        Collection&lt;? extends Route> visited() {\n            return new HashSet&lt;Route>() {{ \n                addAll(space(Dir.F).values());\n                addAll(space(Dir.B).values());\n            }};\n        }\n        \n        \/**\n         * checks if two(forward\/backward) search spaces has met. You can suppose that a route between the\n         * two search spaces is found.\n         * @return returns true if the two search spaces has met otherwise returns false\n         *\/\n        boolean mutual() {\n           return node != null;\n        }\n        \n        \/**\n         * Update the existing values to the specified mu and node if the value of specified mu is less than the\n         * existing value. If update is done returns true, otherwise returns false.\n         * The value mu is calculated as follows:\n         * &lt;pre>\n         * df&#91;u] + w(u, x) + db&#91;x]\n         * &lt;\/pre>\n         * df&#91;u] is the distance from the source to the node u in forward search and db&#91;x] is the distance from the\n         * destination to the node x in backward search. And w(u, x) is the distance(weight) from the node u to x\n         * @param mu the cost(length) between the source and destination when the two search spaces is met\n         * @param visit the visit object(x) which is one of visits in frontier when Dijkstra searching\n         * @return returns true if specified parameters reflected on this object otherwise returns false    \n         *\/\n        boolean update(float mu, Visit visit) {\n            if (mu &lt; this.mu) {\n                this.mu = mu; this.node = visit.node();\n            }\n            return node.equals(this.node);\n        }\n        \n        \/**\n         * check if satisfying the mu is greater than or equal to the cost and the node is settled in the forward \n         * and backward search\n         * @return returns true if the forward search and backward search meet\n         *\/\n        boolean satisfied(float cost) {\n            return cost >= mu &amp;&amp; node != null &amp;&amp; contains(node, Dir.F) &amp;&amp; contains(node, Dir.B);\n        }\n        \n        \/**\n         * Returns Route information generated when the two search spaces meet\n         * @return Route information\n         *\/\n        Route route() {\n            return subroute(Dir.F).concat(subroute(Dir.B));\n        }\n\n        \/**\n         * Returns a Route object that has generated when the two search spaces has met\n         * @param dir direction(Forward\/Backward)\n         * @return Route object from the search space(forward\/backward) if two search space doesn't meet returns null\n         *\/\n        Route subroute(Dir dir) {\n            return space(dir).get(node);\n        }\n    }\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\uc2e4\ud589\uacb0\uacfc<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">BidirectionalDijkstra Algorithm\uc744 \uc2e4\ud589\ud588\uc744 \ub54c \uc0dd\uc131\ub418\ub294 Search Space\ub294 \uc608\uc0c1\ud55c \ubc14\uc640 \uac19\uc774 2\uac1c\uc758 \ub3d9\uc2ec\uc6d0 \ud615\ud0dc\ub85c \uad6c\uc131\ub418\uba70 \uc11c\ub85c \ub9cc\ub098\ub294 \uc9c0\uc810\uc5d0\uc11c \ucd9c\ubc1c\uc9c0(\ud310\uad50\uc0ac\uc625)\uc640 \ubaa9\uc801\uc9c0(\uad11\ud654\ubb38\uc0ac\uc625) \uc0ac\uc774\uc758 \ucd5c\uc801\uacbd\ub85c\uac00 \uc0dd\uc131\ub41c\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ub610\ud55c \ud0d0\uc0c9\uc18d\ub3c4\ub294 Dijkstra: 0.5\ucd08(Node Visit: 145,888), BidirectionalDijkstra: 0.28\ucd08(Node Visit: 111,217)\ub85c \uac1c\uc120\ub428\uc744 \ud655\uc778\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<figure class=\"wp-block-gallery aligncenter has-nested-images columns-default is-cropped wp-block-gallery-1 is-layout-flex wp-block-gallery-is-layout-flex\">\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"705\" height=\"690\" data-id=\"1293\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/dijkstra.png\" alt=\"\" class=\"wp-image-1293\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/dijkstra.png 705w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/dijkstra-300x294.png 300w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/dijkstra-276x270.png 276w\" sizes=\"auto, (max-width: 705px) 100vw, 705px\" \/><figcaption class=\"wp-element-caption\">Dijkstra Algorithm<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"584\" height=\"599\" data-id=\"1294\" src=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/bidirectional-dijkstra.png\" alt=\"\" class=\"wp-image-1294\" srcset=\"https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/bidirectional-dijkstra.png 584w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/bidirectional-dijkstra-292x300.png 292w, https:\/\/skanto.co.kr\/wp-content\/uploads\/2024\/05\/bidirectional-dijkstra-263x270.png 263w\" sizes=\"auto, (max-width: 584px) 100vw, 584px\" \/><figcaption class=\"wp-element-caption\">Bidirectional Dijkstra Algorithm<\/figcaption><\/figure>\n<\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">\ub9c8\uce58\uba70&#8230;<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \ucd5c\ub2e8\uac70\ub9ac \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc740 \ud5a5\ud6c4\uc5d0\ub3c4 \uc5ec\ub7ec \ubd84\uc57c\uc5d0 \uc801\uc6a9\ub420 \uac83\uc774\uba70 \ub610\ud55c \ud0d0\uc0c9 \uc18d\ub3c4 \ub610\ud55c \uc911\uc694\ud55c \uacbd\uc7c1\ub825 \uc911\uc758 \ud558\ub098\uac00 \ub420 \uac83\uc774\ub2e4. \uc624\ub298 \uc18c\uac1c\ud55c Bidirectional Dijkstra Algorithm\ub3c4 \ud0d0\uc0c9 \uc18d\ub3c4\ub97c \uac1c\uc120\ud558\uae30 \uc704\ud55c \ud558\ub098\uc758 \uc2dc\ub3c4\ub85c\uc368 \uae30\uc874 \ub300\ube44 \ud68d\uae30\uc801\uc778 \uc18d\ub3c4\uac1c\uc120\uc744 \ubcf4\uc5ec\uc8fc\ub294 \uac83\uc740 \ub9de\ub2e4. \ud558\uc9c0\ub9cc \uc18d\ub3c4\ub97c \uac1c\uc120\ud568\uc73c\ub85c\uc368 \uc2e4\uc2dc\uac04\uc131 \ub3d9\uc801 \uc815\ubcf4\ub97c \ubc18\uc601\ud558\ub294 \uc989, \uc2e4\uc2dc\uac04 \uc18d\ub3c4\uc815\ubcf4\ub97c \ubc18\uc601\ud574\uc11c \ucd5c\uc801\uc758 \uacbd\ub85c\ub97c \ucc3e\uc544\uc8fc\ub294\ub370\ub294 \ud55c\uacc4\uac00 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uc774\ub7f0 \ubb38\uc81c\uc810\ub4e4\uc5d0 \ub300\ud55c \ud574\uacb0\ucc45\uc73c\ub85c \ub2e4\uc591\ud55c \uc811\uadfc\uc774 \uc774\ub8e8\uc5b4\uc9c0\uace0 \uc788\uc73c\uba70 \ucd5c\uadfc\uc5d0\ub294 \uad50\ud1b5\uacf5\ud559\uc801\uc778 \uac1c\ub150\uc744 \uc811\ubaa9\uc2dc\ud0a8 Contraction Hierarchy\uc640 \uac19\uc740 \uae30\uc220\ub4e4\uc774 \ub098\uc624\uace0 \uc788\ub2e4. \uad6d\ub0b4\uc5d0\ub3c4 \uc774 \uae30\uc220\uc744 \uc774\uc6a9\ud558\uc5ec \ub0b4\ube44\uac8c\uc774\uc158 \uacbd\ub85c\ud0d0\uc0c9\uc5d0 \uc811\ubaa9\ud558\ub294 \uc2dc\ub3c4\ub4e4\uc774 \ub298\uc5b4\ub098\uace0 \uc788\uc73c\uba70 \uad6c\uae00\ub9f5\uacfc \uac19\uc740 \uae00\ub85c\ubc8c \uae30\uc5c5\ub4e4\uc740 \uc774\ubbf8 \uc774\ub7f0 \uae30\uc220\uc744 \uc801\uc6a9\ud558\uace0 \uc788\ub294 \uac83\uc73c\ub85c \uc54c\ub824\uc838 \uc788\ub2e4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\ud5a5\ud6c4 \uae30\ud68c\uac00 \ub418\uba74 Contraction Hierarchy \uae30\uc220\uc5d0 \ub300\ud574 \uc790\uc138\ud558\uac8c \ub2e4\ub904 \ubcf4\uace0\uc790 \ud55c\ub2e4.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\ucc38\uace0\uc790\ub8cc<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/www.homepages.ucl.ac.uk\/~ucahmto\/math\/2020\/05\/30\/bidirectional-dijkstra.html\">Bidirectional Dijkstra<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/www.cs.princeton.edu\/courses\/archive\/spr06\/cos423\/Handouts\/EPP%20shortest%20path%20algorithms.pdf\">Efficient Point-to-Point Shortest Path Algorithms<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/jlazarsfeld.github.io\/ch.150.project\/sections\/1-intro\/\"><strong>Contraction Hierarchies<\/strong>: An Illustrative Guide<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Dijkstra Algorithm\uc740 \ub0b4\ube44\uac8c\uc774\uc158\uc758 \uae38\ucc3e\uae30 \ubfd0\ub9cc \uc544\ub2c8\ub77c \ucd5c\ub2e8\uac70\ub9ac\ub97c \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \uc798 \uc54c\ub824\uc838 \uc788\ub2e4. Dijkstra Algorithm\uc740 \ucd9c\ubc1c\uc9c0\uc640 \ubaa9\uc801\uc9c0 \uc0ac\uc774\uc758 \ucd5c\ub2e8 \uac70\ub9ac \ud0d0\uc0c9\uc744 \ubcf4\uc7a5\ud558\uae34 \ud558\uc9c0\ub9cc \ud0d0\uc0c9 \uac70\ub9ac\uac00 \uba40\uba74 \uba40\uc218\ub85d \uc18c\uc694\ub418\ub294 \uc2dc\uac04\ub3c4 \ube44\ub840\uc801\uc73c\ub85c \uc99d\uac00\ud55c\ub2e4\ub294 \uac83\uc774 \ub9f9\uc810\uc774\ub2e4. \uc774\ub7f0 \ubb38\uc81c\uc810\uc744 \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub2e4\uc591\ud55c \ubc29\ubc95\ub4e4\uc774 \uc2dc\ub3c4 \ub418\uc5c8\uc73c\uba70 \uadf8 \uc911 \ub300\ud45c\uc801\uc778 \uac83\uc774 A*\uc640 \uc591\ubc29\ud5a5 \ud0d0\uc0c9\uc774\ub77c \ud560 \uc218 \uc788\ub2e4. \uc774 \uae00\uc5d0\uc11c\ub294 \ub0b4\ube44\uac8c\uc774\uc158 \uc5c5\uacc4\uc5d0\uc11c \uc8fc\ub85c \uc801\uc6a9\ud558\uace0 A*\uc54c\uace0\ub9ac\uc998\ubcf4\ub2e4 \ucd5c\uc801 \uacbd\ub85c \ud0d0\uc0c9\uc744 \ubcf4\uc7a5\ud558\uba74\uc11c \ud0d0\uc0c9\uc2dc\uac04\uc744 \uac70\uc758 \uc808\ubc18\uc73c\ub85c \uc904\uc77c \uc218 \uc788\ub294 \uc591\ubc29\ud5a5 \ud0d0\uc0c9(Bidirectional Dijkstra Algorithm)\uc744 \uc790\uc138\ud788 \uc54c\uc544\ubcf4\uace0\uc790 \ud55c\ub2e4. \ucc38\uace0\ub85c Dijkstra Algorithm\uc5d0 \ub300\ud574 \uc774\ud574\uac00 \ud544\uc694\ud558\ub2e4\uba74&#8230;<\/p>\n<p class=\"read-more\"><a class=\"btn btn-default\" href=\"https:\/\/skanto.co.kr\/?p=1256\"> 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,114,112,137],"class_list":["post-1256","post","type-post","status-publish","format-standard","hentry","category-sw-development","category-7","tag-bidirectional-dijkstra","tag-dijkstra","tag-112","tag-137"],"_links":{"self":[{"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/1256","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=1256"}],"version-history":[{"count":31,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/1256\/revisions"}],"predecessor-version":[{"id":1357,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=\/wp\/v2\/posts\/1256\/revisions\/1357"}],"wp:attachment":[{"href":"https:\/\/skanto.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1256"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/skanto.co.kr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}