{"id":4378,"date":"2019-06-08T10:59:17","date_gmt":"2019-06-08T09:59:17","guid":{"rendered":"http:\/\/roboblog.fatal-fury.de\/?p=4378"},"modified":"2019-07-01T13:00:54","modified_gmt":"2019-07-01T12:00:54","slug":"graph-basics-of-shortest-paths","status":"publish","type":"post","link":"http:\/\/roboblog.fatal-fury.de\/?p=4378","title":{"rendered":"Graph - Basics of shortest paths"},"content":{"rendered":"

Shortcut links:
\nBasic graph definitions<\/a>
\nBasics of shortest paths (this page)<\/p>\n

Path lengths and distances<\/h2>\n

Sei 𝐺 = (𝑉, 𝐴) ein einfacher, gerichteter Graph und f\u00fcr jede Kante 𝑎 ∈ 𝐴 sei 𝑙(𝑎) eine reale Nummer und die L\u00e4nge<\/strong> von 𝑎.<\/p>\n

    \n
  1. Die L\u00e4nge<\/strong> von einem gew\u00f6hnlichen Path (inklusive gew\u00f6hnliche cycles) ist die Summe von den L\u00e4ngen von allen Kanten in diesem Path.<\/li>\n
  2. Abh\u00e4ngig vom Kontext, die L\u00e4nge<\/strong> von einem generalized Path (inklusive generalized cycles) ist entweder definiert identisch zu gew\u00f6hnlichen Pathen, oder die L\u00e4nge der backwards Kanten werden nicht addiert, sondern subtrahiert.<\/li>\n
  3. Wenn die L\u00e4nge von einem gew\u00f6hnlichen oder generalizedn Cycle negativ ist, wird dieser Cycle einen negativen cycle<\/strong> genannt.<\/li>\n
  4. F\u00fcr zwei Knoten 𝑠,𝑡 ∈ 𝑉, ein k\u00fcrzester Path<\/strong> von 𝑠 nach 𝑡 ist ein (𝑠,𝑡)-path mit minimaler L\u00e4nge von allen (𝑠,𝑡) Pathe.<\/li>\n
  5. Die Distance<\/strong> von 𝑠 nach 𝑡 ist:\n
      \n
    • +unendlich wenn kein (𝑠,𝑡)-path existiert;<\/li>\n
    • -unendlich wenn es einen negativen cycle entlang (𝑠,𝑡)-path gibt;<\/li>\n
    • Die L\u00e4nge von einem k\u00fcrzesten (𝑠,𝑡)-path sonst;<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

      Note:
      \nIn diesem Kontext sind ungerichtete Graphen als symmetrische gerichtete Graphen anzusehen, so dass zwei gegens\u00e4tzlich gerichtete Kanten die selbe L\u00e4nge haben.
      \nWenn es keine negativen cycles gibt, ist die Distanz von einem Knoten zu sich selbst 0, weil der triviale Path ohne keinen die L\u00e4nge 0 hat. Auf der anderen seite, wenn ein Knoten in einem negativen cycle ist, ist seine Distanz zu sich selbst -unendlich.
      \nWeil durch den negativen cycle ja immer ein Weg mit einer noch k\u00fcrzeren L\u00e4nge gefunden werden kann. Und negativ ist kleiner als Null.<\/p>\n

      Subpath property of shortest paths<\/h2>\n

      Statement<\/strong>: F\u00fcr zwei Knoten 𝑠,𝑡 ∈ 𝑉, sei 𝑝 ein k\u00fcrzester (𝑠,𝑡)-Path. Seit 𝑣,𝑤 ∈ 𝑉 zwei Knoten auf dem Path 𝑝, so dass 𝑣 vor 𝑤 liegt. Dann ist der subpath von 𝑝, von 𝑣 zu 𝑤 ein k\u00fcrzester (𝑣,𝑤)-Path.<\/p>\n

      Beweis<\/strong>: Seien 𝑝1<\/sub>, 𝑝2<\/sub> und 𝑝3<\/sub> die Subpathe von 𝑝 von 𝑠 nach 𝑣, von 𝑣 nach 𝑤 und von 𝑤 nach 𝑡. F\u00fcr einen Widerspruchsbeweis angenommen, es gibt einen (𝑣,𝑤)-paht 𝑝2<\/sub>' der k\u00fcrzer ist als 𝑝2<\/sub>. Dann w\u00fcrde die Aneinanderreihung der Pathe 𝑝1<\/sub>+𝑝2<\/sub>'+𝑝3<\/sub> einen k\u00fcrzeren (𝑠,𝑡)-path als 𝑝 ergeben. Da 𝑝 aber schon der k\u00fcrzeste (𝑠,𝑡)-path ist, ist dies ein Widerspruch.
      \nDie Subpathe eines k\u00fcrzesten Pathes sind ebenfalls k\u00fcrzeste Pathe.<\/p>\n

      Anmerkung<\/strong>: Gew\u00f6hnlich wird nur der Fall v=s beachtet. Also dass es nur zwei Pathe gibt und die Argumentation mit dem ersten Path gemacht wird. Diese Version wird auch prefix property<\/strong> genannt.<\/p>\n

      Valid distance property<\/h2>\n

      Definition<\/strong>: F\u00fcr jeden Knoten 𝑢 ∈ sei 𝑑(𝑢) eine real Zahl. Irgendeinen Zahl, muss nicht die Distanz sein. Das valid distance property<\/strong> wird erf\u00fcllt, wenn 𝑑(𝑤) ≤ 𝑑(𝑣) + l(𝑣,𝑤) f\u00fcr alle Kanten (𝑣,𝑤) ∈ 𝐴.
      \nDas ist einfach so eine Definition.<\/p>\n

      Statement<\/strong>: Sei 𝑠 aus 𝑉 und f\u00fcr jeden Knoten 𝑢 aus 𝑉 sei d(𝑢) die Distanz von 𝑠 nach 𝑢 unter Beachtung der Kantenl\u00e4ngen 𝑙.
      \nEs sei d(𝑤) ≤ d(𝑣) + 𝑙(𝑣,𝑤) F\u00fcr alle Kanten (𝑣,𝑤) aus 𝐴.
      \nDas valid distance property ist erf\u00fcllt f\u00fcr k\u00fcrzeste Wege mit Kantenl\u00e4ngen im Graph. <\/p>\n

      Hei\u00dft auf gut deutsch, dass es eine \"k\u00fcrzeste\" Kante von 𝑣 nach 𝑤 gibt und alle anderen Kanten von 𝑣 nach 𝑤 sind l\u00e4nger. Und da 𝑣 ja beliebig sein kann, hei\u00dft es: Es gibt einen k\u00fcrzesten Weg nach 𝑤 und alle andern sind l\u00e4nger.<\/p>\n

      Beweis<\/strong>: The linke Seite der Ungleichung ist die L\u00e4nge von dem k\u00fcrzesten (𝑠,𝑤) Path.
      \nDie rechte Seite ist die L\u00e4nge von irgendeinem<\/strong> (𝑠,𝑤) Path (also die Aneinanderreihnug von dem k\u00fcrzesten (𝑠,𝑣) Path und einer Kante (𝑣,𝑤))<\/p>\n

      Statement distance update<\/strong>: In den meisten shortest-path algorithmen, f\u00fcr jeden Knoten 𝑣 AUS V gibt es ein Attribut d(𝑣).
      \nDieses Attribut entspricht die L\u00e4nge von einem (s,𝑣) Path und ist die echte Distanz von s zu 𝑣 wenn der Algorithmus terminiert.
      \nIn praktisch allen standard Algorithmen, die folgende Update Operation ist die (einzige) Operation zum updaten des d-Attributs:
      \n1. W\u00e4hle eine Kante (𝑣,w) AUS A
      \n2. Wenn (𝑣,w) das valid distance properts verletzt, also diese Kante einen k\u00fcrzeren Weg zu w erm\u00f6glicht, also d(w) > d(𝑣) + l(𝑣,w) dann setzte d(w) := d(𝑣) + l(𝑣,w)<\/p>\n

      Distances along shortest paths<\/h2>\n

      Sei 𝑠 ∈ 𝑉 und f\u00fcr jeden Knoten 𝑢 ∈ V sei d(𝑢) die Distanz von 𝑠 nach 𝑢 unter Ber\u00fccksichtigung der Kantenl\u00e4ngen 𝑙.<\/p>\n

      Statement<\/strong>: Angenommen es gibt keine negativen Cyclen. F\u00fcr eine Kante (𝑣,𝑤), es ist d(𝑤) = d(𝑣) + 𝑙(𝑣,𝑤) genau dann wenn die Kante (𝑣,𝑤) die letzte Kante von einem k\u00fcrzesten (𝑠,𝑤) Path ist.<\/p>\n

      Beweis<\/strong>: <\/p>\n

        \n
      1. Fall d(w) =<\/strong> d(v) + l(v,w)
        \nDann hat die Aneinanderreihung von dem k\u00fcrzesten Path von s nach v und (v,w) die L\u00e4nge d(w) und damit die k\u00fcrzeste L\u00e4nge. (Weil die Kante (v,w) eben die letzte Kante im (s,w) Path ist.\n<\/li>\n
      2. Fall d(w) !=<\/b> d(v) + l(v,w)
        \nWegen dem valid distanz property ist d(w) < d(v) + l(v,w) (Wenn der Path nicht \u00fcber die k\u00fcrzeste kante geht, dann \u00fcber eine L\u00e4ngere, also ist die Distanz auch gr\u00f6\u00dfer als die k\u00fcrzeste Distanz d(w)).\nF\u00fcr einen Widerspruchsbeweis angenommen, dass ein k\u00fcrzester (s,w) Path ist von der Form p + (v,w). Dann hat p die L\u00e4nge d(w) - l(v,w) < d(v) was ein Widerspruch zur Definition von d(v) ist.<\/li>\n<\/ol>\n

        Reconstruction of a shortest path from the distances<\/h2>\n

        Angenommen, dass f\u00fcr die Knoten 𝑠,𝑡 ∈ V die Distanz d𝑠<\/sub>(t) von 𝑠 to 𝑡 unter Beachtung der Kantenl\u00e4ngen l, welche eine reale Nummer ist (weder +inf noch -inf). Dann kann ein k\u00fcrzester (𝑠,𝑡) Path 𝑝 wie folgt konstruiert werden.<\/p>\n

          \n
        1. Initialisiere 𝑝 als leer<\/li>\n
        2. Setzte 𝑤 := 𝑡 - Wir konstruieren den Path r\u00fcckw\u00e4rts von 𝑡 nach 𝑠<\/li>\n
        3. While w \/= s\n
            \n
          1. Finde eine Kante (𝑣,𝑤), so dass d𝑠<\/sub>(𝑤) = d𝑠<\/sub>(𝑣) + l(𝑣,𝑤) <\/li>\n
          2. F\u00fcge die Kante (𝑣,𝑤) an den Anfang von 𝑝 an<\/li>\n
          3. Setze 𝑤 := 𝑣<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n

            Constructing a shortest-paths arborescence or a negative cycle<\/h2>\n

            Wie beim Valid distance property erw\u00e4hnt, benutzen die meisten Algorithmen f\u00fcr das k\u00fcrzeste Wege Probleme eine Standard Update Operation. Diese Operation kann wie folgt erweitert werden (mit 𝑠 f\u00fcr den Startknoten).
            \nJeder Knoten v ∈ V speichert eine<\/strong> von den incoming Kanten als zus\u00e4tzliches Attribut:<\/p>\n

              \n
            1. Initialisierung des Attributs:
              \nDieses Attribut wird f\u00fcr den Knoten s mit void initialisiert.
              \nF\u00fcr alle anderen Knoten v, die mit d(v) = +inf initialisiert wurden, wird dieses Attribut auch mit void initialisiert.<\/p>\n

              Je nachdem ob die ausgehenden Kanten von s bei der Initialisierung beachtet, oder erst w\u00e4hrend der Iteration, ist die Distanz der abgehenden Knoten von s damit nicht +inf.
              \nUnd das zus\u00e4tzliche Attribut dieser Knoten wird mit der initial incoming Kante (s,v) initialisiert.\n<\/li>\n

            2. Update: Wann immer die Standard Update Operation auf eine Kante (v,w) angewendet wird (also das Aktualisieren von der Distanz), wird diese Kante (v,w) die incoming Kante von W. Also speichert das zus\u00e4tzliche Attribut immer die zuletzt gesehene Kante.<\/li>\n<\/ol>\n

              Statement<\/strong>:
              \nBetrachte ein Algorithmus welcher ein k\u00fcrzesten (s,v) Path f\u00fcr jeden Knoten v ∈ V liefert, dabei sind die die Distanzen von s eine real Nummer (weder -inf noch +inf). <\/p>\n

              Bei Terminierung gelten folgende Statements:<\/p>\n

                \n
              1. Die incoming Kante von s ist void genau dann wenn s nicht auf einem negative cycle Paht liegt. (Das ist auch so, selbst wenn s auf einem positive cycle Path liegt. Weil der k\u00fcrzeste Weg von s nach t geht nicht nochmal \u00fcber s.)<\/li>\n
              2. Die gespeicherten Kanten in dem zus\u00e4tzlichen Attribut bilden ein cycle genau dann wenn die erreichten Knoten einen negativen Cycle bilden. (Einen positiven cycle bilden die Knoten ja nicht, das wissen wir bereits.)
                \n Jeder cycle in diesen ausgew\u00e4hlten Kanten ist ein negative cycle. (Weil es positive Cycle ja nicht gibt)<\/li>\n
              3. Wenn die erreichten Knoten von s aus keinen negativen cycle enth\u00e4lt (Und positive cycle haben wir ja nicht), dann bilden die gew\u00e4hlten Kanten eine arborescene bei der der Knoten s die Wurzel ist und die arborescene spannt \u00fcber alle erreichten Knoten.
                \nF\u00fcr jeden erreichbaren Knoten v ∈ V, der Path von s zu v in dieser Arborescene ist ein k\u00fcrzester (s,v)-Path. (Ja was sonst wenn man einen shortest-path Algo laufen l\u00e4sst.)<\/li>\n<\/ol>\n

                (Was ist das Problem mit negativne cycle bei andern Algos? Die Terminieren nicht?)<\/p>\n

                Beweis<\/strong>:
                \nDer Algorithmus liefert d(s) < 0 genau dann wenn s auf einem negativen cycle ist. (Positive cycle gibts ja nicht und sonst ist d(s) > 0). Genau in diesem Fall wird die incoming Kante von s geupdated.
                \nDas Beweis Statement Satz 1. (Zur Erinnerung: Satz 1: Die incoming Kante von s ist void wenn NICHT negative cycle. Wenn nicht dann void.)<\/p>\n

                (Aber woher wissen wir, dass der Algo das denn auch wirklich tut?)<\/p>\n

                F\u00fcr den 2. Satz beachte erst, dass der zweite Satz impliziert den only-if Teil von dem ersten Satz, so m\u00fcssen wir nicht den only-if Teil von dem ersten Satz beachten.
                \nSei v ein erreichbarer Knoten auf einen negative cycle. Sei p ein Path auf ausgew\u00e4hlten Kanten welcher in v endet.
                \nIm Besonderen, lass p eine maximale anzahl voN Kanten von allen m\u00f6glichen dieser Pathe.
                \nDann p kann nicht an s starte, weil der algorithmus wird eine distanz Wert f\u00fcr v liefern, welcher kleiner ist als die echte Distanz.
                \nKlar, p cann nicht an einem unreachable Knoten starten. Super Klar.<\/p>\n

                (Admissible\/zul\u00e4ssige) node potentials<\/h2>\n

                F\u00fcr jeden Knoten 𝑣 ∈ 𝑉, sei h(𝑣) eine reale Nummer.
                \nF\u00fcr Kante 𝑎 = (𝑣,𝑤) ∈ 𝐴, sei 𝑙h<\/sup>(𝑎) := 𝑙(𝑎) - h(𝑣) + h(𝑤)
                \nIn diesem Kontext, diese Werte werden gew\u00f6hnliche node potential genannt.
                \nNode potentials sind zul\u00e4ssig wenn 𝑙(𝑎) >= 0 f\u00fcr alle 𝑎 ∈ 𝐴. Also Kantengewicht(l\u00e4nge) positiv ist.<\/p>\n

                Statement:<\/strong>
                \nEin (𝑠,𝑡)-path ist k\u00fcrzer als ein anderer (𝑠,𝑡)-path unter der Ber\u00fccksichtigung der Kantenl\u00e4ngen 𝑙h<\/sup>, genau dann wenn die selbe Aussage auch wahr ist f\u00fcr die Kantenl\u00e4ngen 𝑙. Also die shortest path Algorithmen funktionieren auch weiterhin.
                \nIm Besonderen, der k\u00fcrzeste Path unter Ber\u00fccksichtigung der Kantenl\u00e4ngen 𝑙h<\/sup> ist exakt der selbe k\u00fcrzeste Path unter Beachtung der Kantenl\u00e4ngen 𝑙. Also die Algorithmen geben sogar das selbe Ergebnis zur\u00fcck. Wir haben nichts kaputt gemacht. Nur verbesser. <\/p>\n

                Beweis:<\/strong>
                \nSet 𝑠 = 𝑣1<\/sub> - 𝑣2<\/sub> - ... - 𝑣k<\/sub> = 𝑡 die Knoten auf einem (𝑠,𝑡)-path. Gemein ist dass s = 𝑣1<\/sub> und t = 𝑣k<\/sub>
                \nDie L\u00e4nge auf diesem Path unter Ber\u00fccksichtigung von 𝑙h<\/sup> ist dann *einsetzen und umformen von 𝑙h<\/sup> und 𝑙 *
                \nAlso: Die L\u00e4nge von einem (𝑠,𝑡)-path unter Ber\u00fccksichtigung von 𝑙h<\/sup> und 𝑙, unterscheidet sich nur durch eine Konstante h(𝑡) - h(𝑠).<\/p>\n

                Ist ja auch klar: Wenn f\u00fcr jede Kante h(𝑣) subtrahiert und h(𝑤) addiert wird, und bei der n\u00e4chsten Kante im Path w mit dem n\u00e4chsten v tauscht. Dann heben sich die Termen in dieser Summe bis auf den ersten und letzten auf.<\/p>\n

                Anmerkung:<\/strong>
                \nAdmissible\/zul\u00e4ssige node potential erm\u00f6glichen effiziente Algorithmen wie Dijkstra, welche nicht-negative Kanten L\u00e4ngen erwarten. Durch die node potentials kann man negative Kanten L\u00e4ngen ins positive ziehen.<\/p>\n

                G
                \n𝐺
                \nV
                \n𝑉
                \nA
                \n𝐴
                \nE
                \n𝐸
                \nK
                \n𝐾
                \na
                \n𝑎
                \nk
                \n𝑘
                \nl
                \n𝑙
                \nm
                \n𝑚
                \nn
                \n𝑛
                \np
                \n𝑝
                \ns
                \n𝑠
                \nt
                \n𝑡
                \nu
                \n𝑢
                \nv
                \n𝑣
                \nw
                \n𝑤
                \nTeilemenge
                \n⊆
                \nphi
                \nφ
                \nElement von
                \n∈<\/p>\n","protected":false},"excerpt":{"rendered":"

                Shortcut links: Basic graph definitions Basics of shortest paths (this page) Path lengths and distances Sei 𝐺 = (𝑉, 𝐴) ein einfacher, gerichteter Graph und f\u00fcr jede Kante 𝑎 ∈ 𝐴 sei 𝑙(𝑎) eine reale Nummer und die L\u00e4nge von 𝑎. Die L\u00e4nge von einem gew\u00f6hnlichen Path (inklusive gew\u00f6hnliche cycles) ist die Summe von den […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-4378","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4378","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4378"}],"version-history":[{"count":30,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4378\/revisions"}],"predecessor-version":[{"id":4457,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4378\/revisions\/4457"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4378"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4378"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4378"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}