{"id":5475,"date":"2018-12-28T15:53:34","date_gmt":"2018-12-28T06:53:34","guid":{"rendered":"https:\/\/www.lancard.com\/blog\/?p=5475"},"modified":"2025-03-12T11:26:05","modified_gmt":"2025-03-12T02:26:05","slug":"recursivedistance","status":"publish","type":"post","link":"https:\/\/www.lancard.com\/blog\/2018\/12\/28\/recursivedistance\/","title":{"rendered":"\u518d\u5e30\u7684\u554f\u3044\u5408\u308f\u305b\u3067\u3001\u8907\u6570\u70b9\u9593\u306e\u7d4c\u8def\u7684\u306a\u4f7f\u3044\u65b9"},"content":{"rendered":"<p>\u5c11\u3057\u3060\u3051\u6642\u9593\u304c\u51fa\u6765\u305f\u306e\u3067\u3001\u4ee5\u524d\u4f7f\u304a\u3046\u304b\u8ff7\u3063\u3066\u3044\u305fPostgreSQL\u306eWITH RECURSIVE\u3092\u4f7f\u3063\u3066\u8907\u6570\u70b9\u9593\u306e\u79fb\u52d5\u7d4c\u8def\u3068\u8ddd\u96e2\u3092\u6c42\u3081\u308b\u3088\u3046\u306aSQL\u3092\u4f5c\u3063\u3066\u307f\u307e\u3057\u305f\u3002<br \/>\n\u203b\u4f7f\u304a\u3046\u3068\u601d\u3063\u3066\u305f\u7b87\u6240\u306f\u3001\u8a08\u7b97Cost\u304c\u554f\u984c\u306b\u306a\u308a\u305d\u3046\u3060\u3063\u305f\u306e\u3067\u3001\u7d50\u5c40group\u5316\u3059\u308b\u5217\u3092\u8ffd\u52a0\u3057\u3066\u5bfe\u5fdc\u3057\u307e\u3057\u305f\u304c\u3002<\/p>\n<p><!--more--><\/p>\n<p>\u3042\u308b\u5730\u70b9\u304b\u3089\u5225\u306e\u5730\u70b9\u3078\u884c\u3051\u308b\u7d44\u5408\u305b\u3092\u767b\u9332\u3059\u308b\u30c6\u30fc\u30d6\u30eb\u3092\u4f5c\u308a\u307e\u3059\u3002<\/p>\n<pre code=\"SQL\">\nCREATE TABLE public.pair(\n    p1 text, -- \u958b\u59cb\u5730\u70b9\n    p2 text, -- \u5230\u9054\u5730\u70b9\n    distance integer -- \u8ddd\u96e2\n);\n<\/pre>\n<p>\u4ee5\u4e0b\u306e\u30c7\u30fc\u30bf\u3092\u4f5c\u308a\u3001\u8ddd\u96e2\u306f\u30e9\u30f3\u30c0\u30e0\u306b\u5165\u308c\u307e\u3057\u305f\u3002<\/p>\n<pre code=\"SQL\">\np1  p2  distance\nA   B   8\nC   K   91\nD   B   66\nE   D   78\nF   E   44\nG   F   36\nH   G   2\nI   H   23\nJ   H   94\nM   K   28\n<\/pre>\n<p>\u4eca\u56de\u306f\u9006\u9806\u3067p2\u304b\u3089p1\u3078\u3082\u540c\u3058\u8ddd\u96e2distance\u3067\u884c\u304f\u4e8b\u3092\u53ef\u3068\u3057\u307e\u3057\u305f\u306e\u3067\u3001\u3053\u308c\u3092view\u3067\u5bfe\u5fdc\u3057\u307e\u3059\u3002<\/p>\n<pre code=\"SQL\">\nCREATE OR REPLACE VIEW public.pair2 AS \n SELECT p1, p2, distance FROM pair\n UNION\n  SELECT p2 AS p1,p1 AS p2, distance FROM pair\n;\n<\/pre>\n<p>\u3053\u306epair2\u306b\u5bfe\u3057\u3066\u518d\u5e30\u554f\u3044\u5408\u308f\u305b\u3092\u4f7f\u3063\u3066\u307f\u307e\u3059\u3002<br \/>\n\u30fb\u4eca\u56de\u306f\u6570\u304c\u591a\u304f\u306a\u3044\u306e\u3067\u7e70\u308a\u8fd4\u3057\u56de\u6570\u7121\u5236\u9650\u3067\u3082\u826f\u3044\u3093\u3067\u3059\u304c\u3001\u4e00\u5fdc10\u56de\u672a\u6e80\u3068\u3059\u308b\u305f\u3081n\u5217\u3092\u8ffd\u52a0\u3057\u307e\u3059\u3002<br \/>\n\u30fb\u307e\u305f\u3001\u9014\u4e2d\u306e\u7d4c\u8def\u304c\u5206\u304b\u3089\u306a\u3044\u306e\u3082\u5fae\u5999\u3060\u3063\u305f\u306e\u3067\u3001route\u914d\u5217\u3092\u8ffd\u52a0\u3057\u307e\u3059\u3002<\/p>\n<pre code=\"SQL\">\nWITH RECURSIVE r AS(\n    SELECT p1,p2,distance\n        ,1 as n\n        , array[p1, p2] AS route\n        FROM pair2\n    UNION\n        SELECT r.p1, p.p2, r.distance+p.distance as distance,n+1\n        , route||array[p.p2]\n        FROM pair2 p\n        JOIN r ON p.p1 = r.p2 -- \u95a2\u9023key\n        AND r.p1 != p.p2 -- \u540c\u3058\u5024\u306f\u4e0d\u8981\n        AND NOT(p.p2 = ANY(route)) -- \u4e00\u5ea6\u901a\u3063\u305f\u5834\u6240\u306f\u901a\u3089\u306a\u3044\n        WHERE n+1 < 10 -- \u7d99\u7d9a\u56de\u6570\u3092\u6307\u5b9a\n) SELECT * FROM r\n WHERE p1 = 'A'\nORDER BY p1,p2,n,distance;\n<\/pre>\n<p>\u7d50\u679c\u3067\u3059\u3002<br \/>\ndistance\u304c\u52a0\u7b97\u3055\u308c\u3066\u884c\u3063\u3066\u308b\u306e\u304c\u5206\u304b\u308a\u307e\u3059\u3002<br \/>\n\u307e\u305fA\u3068C,K,M\u306f\u95a2\u9023\u30c7\u30fc\u30bf\u304c\u7121\u3044\u306e\u3067\u3001\u7d4c\u8def\u306f\u51fa\u3066\u3044\u307e\u305b\u3093\u3002<\/p>\n<pre code=\"SQL\">\np1  p2  distance    n   route\nA   B   8   1   {A,B}\nA   D   74  2   {A,B,D}\nA   E   152 3   {A,B,D,E}\nA   F   196 4   {A,B,D,E,F}\nA   G   232 5   {A,B,D,E,F,G}\nA   H   234 6   {A,B,D,E,F,G,H}\nA   I   257 7   {A,B,D,E,F,G,H,I}\nA   J   328 7   {A,B,D,E,F,G,H,J}\n<\/pre>\n<a class=\"synved-social-button synved-social-button-share synved-social-size-24 synved-social-resolution-single synved-social-provider-facebook nolightbox\" data-provider=\"facebook\" target=\"_blank\" rel=\"nofollow\" title=\"Share on Facebook\" href=\"https:\/\/www.facebook.com\/sharer.php?u=https%3A%2F%2Fwww.lancard.com%2Fblog%2Fwp-json%2Fwp%2Fv2%2Fposts%2F5475&amp;t=%E5%86%8D%E5%B8%B0%E7%9A%84%E5%95%8F%E3%81%84%E5%90%88%E3%82%8F%E3%81%9B%E3%81%A7%E3%80%81%E8%A4%87%E6%95%B0%E7%82%B9%E9%96%93%E3%81%AE%E7%B5%8C%E8%B7%AF%E7%9A%84%E3%81%AA%E4%BD%BF%E3%81%84%E6%96%B9&amp;s=100&amp;p[url]=https%3A%2F%2Fwww.lancard.com%2Fblog%2Fwp-json%2Fwp%2Fv2%2Fposts%2F5475&amp;p[images][0]=&amp;p[title]=%E5%86%8D%E5%B8%B0%E7%9A%84%E5%95%8F%E3%81%84%E5%90%88%E3%82%8F%E3%81%9B%E3%81%A7%E3%80%81%E8%A4%87%E6%95%B0%E7%82%B9%E9%96%93%E3%81%AE%E7%B5%8C%E8%B7%AF%E7%9A%84%E3%81%AA%E4%BD%BF%E3%81%84%E6%96%B9\" style=\"font-size: 0px;width:24px;height:24px;margin:0;margin-bottom:5px;margin-right:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"Facebook\" title=\"Share on Facebook\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"24\" height=\"24\" style=\"display: inline;width:24px;height:24px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"https:\/\/www.lancard.com\/blog\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/48x48\/facebook.png\" \/><\/a><a class=\"synved-social-button synved-social-button-share synved-social-size-24 synved-social-resolution-single synved-social-provider-twitter nolightbox\" data-provider=\"twitter\" target=\"_blank\" rel=\"nofollow\" title=\"Share on Twitter\" href=\"http:\/\/twitter.com\/share?url=https%3A%2F%2Fwww.lancard.com%2Fblog%2Fwp-json%2Fwp%2Fv2%2Fposts%2F5475&amp;text=%E5%86%8D%E5%B8%B0%E7%9A%84%E5%95%8F%E3%81%84%E5%90%88%E3%82%8F%E3%81%9B%E3%81%A7%E3%80%81%E8%A4%87%E6%95%B0%E7%82%B9%E9%96%93%E3%81%AE%E7%B5%8C%E8%B7%AF%E7%9A%84%E3%81%AA%E4%BD%BF%E3%81%84%E6%96%B9\" style=\"font-size: 0px;width:24px;height:24px;margin:0;margin-bottom:5px;margin-right:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"twitter\" title=\"Share on Twitter\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"24\" height=\"24\" style=\"display: inline;width:24px;height:24px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"https:\/\/www.lancard.com\/blog\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/48x48\/twitter.png\" \/><\/a><a class=\"synved-social-button synved-social-button-share synved-social-size-24 synved-social-resolution-single synved-social-provider-linkedin nolightbox\" data-provider=\"linkedin\" target=\"_blank\" rel=\"nofollow\" title=\"Share on Linkedin\" href=\"https:\/\/www.linkedin.com\/shareArticle?mini=true&amp;url=https%3A%2F%2Fwww.lancard.com%2Fblog%2Fwp-json%2Fwp%2Fv2%2Fposts%2F5475&amp;title=%E5%86%8D%E5%B8%B0%E7%9A%84%E5%95%8F%E3%81%84%E5%90%88%E3%82%8F%E3%81%9B%E3%81%A7%E3%80%81%E8%A4%87%E6%95%B0%E7%82%B9%E9%96%93%E3%81%AE%E7%B5%8C%E8%B7%AF%E7%9A%84%E3%81%AA%E4%BD%BF%E3%81%84%E6%96%B9\" style=\"font-size: 0px;width:24px;height:24px;margin:0;margin-bottom:5px;margin-right:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"linkedin\" title=\"Share on Linkedin\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"24\" height=\"24\" style=\"display: inline;width:24px;height:24px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"https:\/\/www.lancard.com\/blog\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/48x48\/linkedin.png\" \/><\/a><a class=\"synved-social-button synved-social-button-share synved-social-size-24 synved-social-resolution-single synved-social-provider-tumblr nolightbox\" data-provider=\"tumblr\" target=\"_blank\" rel=\"nofollow\" title=\"Share on tumblr\" href=\"https:\/\/tumblr.com\/share?s=&amp;v=3&amp;t=%E5%86%8D%E5%B8%B0%E7%9A%84%E5%95%8F%E3%81%84%E5%90%88%E3%82%8F%E3%81%9B%E3%81%A7%E3%80%81%E8%A4%87%E6%95%B0%E7%82%B9%E9%96%93%E3%81%AE%E7%B5%8C%E8%B7%AF%E7%9A%84%E3%81%AA%E4%BD%BF%E3%81%84%E6%96%B9&amp;u=https%3A%2F%2Fwww.lancard.com%2Fblog%2Fwp-json%2Fwp%2Fv2%2Fposts%2F5475\" style=\"font-size: 0px;width:24px;height:24px;margin:0;margin-bottom:5px;margin-right:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"tumblr\" title=\"Share on tumblr\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"24\" height=\"24\" style=\"display: inline;width:24px;height:24px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"https:\/\/www.lancard.com\/blog\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/48x48\/tumblr.png\" \/><\/a><a class=\"synved-social-button synved-social-button-share synved-social-size-24 synved-social-resolution-single synved-social-provider-mail nolightbox\" data-provider=\"mail\" rel=\"nofollow\" title=\"Share by email\" href=\"mailto:?subject=%E5%86%8D%E5%B8%B0%E7%9A%84%E5%95%8F%E3%81%84%E5%90%88%E3%82%8F%E3%81%9B%E3%81%A7%E3%80%81%E8%A4%87%E6%95%B0%E7%82%B9%E9%96%93%E3%81%AE%E7%B5%8C%E8%B7%AF%E7%9A%84%E3%81%AA%E4%BD%BF%E3%81%84%E6%96%B9&amp;body=%E3%82%B7%E3%82%A7%E3%82%A2%E3%81%99%E3%82%8B%EF%BC%9A:%20https%3A%2F%2Fwww.lancard.com%2Fblog%2Fwp-json%2Fwp%2Fv2%2Fposts%2F5475\" style=\"font-size: 0px;width:24px;height:24px;margin:0;margin-bottom:5px\"><img loading=\"lazy\" decoding=\"async\" alt=\"mail\" title=\"Share by email\" class=\"synved-share-image synved-social-image synved-social-image-share\" width=\"24\" height=\"24\" style=\"display: inline;width:24px;height:24px;margin: 0;padding: 0;border: none;box-shadow: none\" src=\"https:\/\/www.lancard.com\/blog\/wp-content\/plugins\/social-media-feather\/synved-social\/image\/social\/regular\/48x48\/mail.png\" \/><\/a>","protected":false},"excerpt":{"rendered":"<p>\u5c11\u3057\u3060\u3051\u6642\u9593\u304c\u51fa\u6765\u305f\u306e\u3067\u3001\u4ee5\u524d\u4f7f\u304a\u3046\u304b\u8ff7\u3063\u3066\u3044\u305fPostgreSQL\u306eWITH RECURSIVE\u3092\u4f7f\u3063\u3066\u8907\u6570\u70b9\u9593\u306e\u79fb\u52d5\u7d4c\u8def\u3068\u8ddd\u96e2\u3092\u6c42\u3081\u308b\u3088\u3046\u306aSQL\u3092\u4f5c\u3063\u3066\u307f\u307e\u3057\u305f\u3002 \u203b\u4f7f\u304a\u3046\u3068\u601d\u3063\u3066\u305f\u7b87\u6240\u306f\u3001\u8a08\u7b97Cost\u304c\u554f\u984c\u306b\u306a\u308a [&hellip;]<\/p>\n","protected":false},"author":17,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,1],"tags":[],"class_list":["post-5475","post","type-post","status-publish","format-standard","hentry","category-postgresql","category-1"],"_links":{"self":[{"href":"https:\/\/www.lancard.com\/blog\/wp-json\/wp\/v2\/posts\/5475","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lancard.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lancard.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lancard.com\/blog\/wp-json\/wp\/v2\/users\/17"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lancard.com\/blog\/wp-json\/wp\/v2\/comments?post=5475"}],"version-history":[{"count":3,"href":"https:\/\/www.lancard.com\/blog\/wp-json\/wp\/v2\/posts\/5475\/revisions"}],"predecessor-version":[{"id":5478,"href":"https:\/\/www.lancard.com\/blog\/wp-json\/wp\/v2\/posts\/5475\/revisions\/5478"}],"wp:attachment":[{"href":"https:\/\/www.lancard.com\/blog\/wp-json\/wp\/v2\/media?parent=5475"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lancard.com\/blog\/wp-json\/wp\/v2\/categories?post=5475"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lancard.com\/blog\/wp-json\/wp\/v2\/tags?post=5475"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}