Pathfinding

Pathfinding bzw. Wegfindung ist in der Informatik die algorithmengestützte Suche nach dem oder den optimalen Wegen (englisch path – Pfad) von einem gegebenen Startpunkt zu einem oder mehreren Zielpunkten. Die Einsatzgebiete reichen von Netzwerk-Flussanalyse über Routenplanung bis zu Computerspielen.

Aufgabenspektrum

Datei:Pathfinding A Star.svg

Grün: Startfeld
rot: Weg
blau: Zielfeld
grau: Hindernis

In vielen, aber nicht notwendigerweise in allen Fällen ist die Suche nach dem optimalen Weg zwischen zwei Punkten auch die Suche nach der kostengünstigsten oder kürzesten Route mit den wenigsten Hindernissen. Dabei handelt es sich zwar um das „klassische Lernbeispiel“, aber die richtige Antwort auf ein Pathfinding-Problem ist in der Praxis nur selten auch wirklich die Luftlinie zwischen einem gegebenen Start- und einem gegebenen Zielpunkt. Die Suche wird häufig durch andere Faktoren mitbestimmt, die den Begriff des Optimums verzerren und dadurch andere Routen sinnvoller erscheinen lassen, wie z. B.:

nicht oder nur bedingt passierbare Hindernisse, die den direkten Weg versperren
variable Kosten in der Fortbewegung, z. B. für erhöhten Energieverbrauch gegen Strömung
mehrdimensionale Kostenmodelle in der Fortbewegung, z. B. Zeit vs. Energie vs. Gefahren
die Rasterung bzw. Diskretisierung der Umwelt, ähnlich einem Schach- oder Spielfeld
die Notwendigkeit, auf der Route bestimmte Zwischenpunkte zu passieren oder günstige Abbruchmöglichkeiten für die Route offenzulassen
nicht kartesische Koordinaten

Algorithmen

{{#if: Kürzester Pfad|{{#ifexist:Kürzester Pfad|

|{{#if: |{{#ifexist:{{{2}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{2}}}{{#if: ||{{{titel2}}}}}]]{{#if: |{{#ifexist:{{{3}}}| und [[{{{3}}}{{#if: ||{{{titel3}}}}}]]|}}|}}

|{{#if: |{{#ifexist:{{{3}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{3}}}{{#if: ||{{{titel3}}}}}]]

|}}|}}|}}|}}|}}|Einbindungsfehler: Die Vorlage Hauptartikel benötigt immer mindestens ein Argument.}}

Um den Anforderungen an Pathfinding je nach Kontext zu entsprechen, wurde in der Vergangenheit eine Vielzahl von Algorithmen entwickelt, von denen fast alle ihre speziellen Vor- und Nachteile haben.

Eine weit verbreitete Pathfinding-Methode ist der A*-Algorithmus, bei dem die Umgebung als Karte als Graph interpretiert wird und zur Berechnung Heuristiken verwendet werden. Zuerst müssen Start- und Zielknoten festgelegt werden. Danach erhält jedes Feld vom Startpunkt aus einen Wert, der proportional zur Entfernung ansteigt. Der optimale Weg ist derjenige, bei dem das Zielfeld den geringsten Wert erhält. Hindernisse, die zwar zu bewältigen sind, aber einen Zeitverlust aufbringen, können dadurch leicht berücksichtigt werden. (Ein Beispiel dafür wäre ein Sumpf, bei dem der Wert pro Feld beispielsweise 2 statt 1 ansteigt und deshalb möglicherweise ein schnellerer, aber längerer Weg außen herum existiert.)

Hat man keine Heuristik, um die Kosten zwischen Knoten abzuschätzen, kann man statt des A*-Algorithmus den Algorithmus von Dijkstra verwenden. Um alle kürzesten Pfade von einem Knoten zu allen anderen Knoten auch in einem Graphen mit negativen Kantengewichten berechnen zu können, kann der Bellman-Ford-Algorithmus verwendet werden. Sucht man nicht nur die günstigsten Pfade eines Knotens zu allen anderen Knoten im Graph, sondern die günstigsten Pfade zwischen allen Knotenpaaren, so kann man den Min-Plus-Matrixmultiplikations-Algorithmus oder den Algorithmus von Floyd und Warshall verwenden.

Anwendungsbeispiele

Im Computerspiele-Bereich reicht die Historie des Pathfindings von Spiele-Klassikern wie Pac-Man bis in die Gegenwart. Während bei Pac-Man z. B. einfache Pathfinding-Algorithmen dafür sorgten, dass sich Gespenster als Computergegner durch ein virtuelles Labyrinth bewegten, dienen sie heute in Echtzeit-Strategiespielen der Routenplanung ganzer Militärverbände und in Ego-Shootern der ausgefeilten Orientierung computergesteuerter Bot-Gegner. Echtzeit-Strategiespiele basieren in der Regel auf zweidimensionalen Karten, die in einzelne Kacheln unterteilt sind. Besondere Schwierigkeiten ergeben sich z. B. bei Wegen, die dynamisch versperrt werden, etwa wenn mehrere Einheiten gleichzeitig eine enge Passage durchqueren. In Ego-Shootern, bei deren Karten die dritte Dimension eine wichtigere Rolle spielt, wird häufig mit Wegpunkten gearbeitet, an denen sich die Künstliche Intelligenz orientiert. Fast immer ist „gutes“ Pathfinding auch mit hoher Komplexität verbunden. Im Computerspiel Age of Empires II z. B. nahm allein das Pathfinding auf damals handelsüblicher Hardware 60 bis 70 Prozent der gesamten CPU-Leistung während des Spielens in Anspruch.<ref name="aoe"> Gamasutra, Dave C. Pottinger, 2000: <templatestyles src="Webarchiv/styles.css" />{{#if:20081221121604

      | {{#ifeq: 20081221121604 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: „Terrain Analysis in Realtime Strategy Games“ | {{#invoke:WLink|getEscapedTitle|„Terrain Analysis in Realtime Strategy Games“}} | {{#invoke:Webarchiv|getdomain|http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20081221121604}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: „Terrain Analysis in Realtime Strategy Games“ | {{#invoke:WLink|getEscapedTitle|„Terrain Analysis in Realtime Strategy Games“}} | {{#invoke:Webarchiv|getdomain|http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20081221121604}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: „Terrain Analysis in Realtime Strategy Games“ | {{#invoke:WLink|getEscapedTitle|„Terrain Analysis in Realtime Strategy Games“}} | {{#invoke:Webarchiv|getdomain|http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: „Terrain Analysis in Realtime Strategy Games“ | {{#invoke:WLink|getEscapedTitle|„Terrain Analysis in Realtime Strategy Games“}} | {{#invoke:Webarchiv|getdomain|http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: „Terrain Analysis in Realtime Strategy Games“ | {{#invoke:WLink|getEscapedTitle|„Terrain Analysis in Realtime Strategy Games“}} | {{#invoke:Webarchiv|getdomain|http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: „Terrain Analysis in Realtime Strategy Games“ | {{#invoke:WLink|getEscapedTitle|„Terrain Analysis in Realtime Strategy Games“}} | {{#invoke:Webarchiv|getdomain|http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20081221121604|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: „Terrain Analysis in Realtime Strategy Games“
    | {{#if: {{#invoke:WLink|isBracketedLink|„Terrain Analysis in Realtime Strategy Games“}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} (MS Word; 980 kB)</ref>

Entsprechend große Anstrengungen werden unternommen, um Pathfinding-Algorithmen zu optimieren. Die Lösungskonzepte reichen von Vorberechnungen (d. h. Reduzierung der Laufzeit auf Kosten von Speicherbedarf) bis hin zu vorteilhaften Annahmen, die ein Programm bzgl. seines konkreten Anwendungsfalls bereits im Vorfeld treffen kann (z. B. „zwischen A und B liegt eine unüberwindbare Schlucht, über die nur eine einzige Brücke führt, also wird die Route zwangsläufig dort entlang führen und nicht woanders“).<ref name="tum3d"><templatestyles src="Webarchiv/styles.css" />{{#if:20070607025234

      | {{#ifeq: 20070607025234 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: 3D Pathfinding | {{#invoke:WLink|getEscapedTitle|3D Pathfinding}} | {{#invoke:Webarchiv|getdomain|http://3dpathfinding.homeunix.org/}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20070607025234}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: 3D Pathfinding | {{#invoke:WLink|getEscapedTitle|3D Pathfinding}} | {{#invoke:Webarchiv|getdomain|http://3dpathfinding.homeunix.org/}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20070607025234}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: 3D Pathfinding | {{#invoke:WLink|getEscapedTitle|3D Pathfinding}} | {{#invoke:Webarchiv|getdomain|http://3dpathfinding.homeunix.org/}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: 3D Pathfinding | {{#invoke:WLink|getEscapedTitle|3D Pathfinding}} | {{#invoke:Webarchiv|getdomain|http://3dpathfinding.homeunix.org/}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: 3D Pathfinding | {{#invoke:WLink|getEscapedTitle|3D Pathfinding}} | {{#invoke:Webarchiv|getdomain|http://3dpathfinding.homeunix.org/}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: 3D Pathfinding | {{#invoke:WLink|getEscapedTitle|3D Pathfinding}} | {{#invoke:Webarchiv|getdomain|http://3dpathfinding.homeunix.org/}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20070607025234|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://3dpathfinding.homeunix.org/}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: 3D Pathfinding
    | {{#if: {{#invoke:WLink|isBracketedLink|3D Pathfinding}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://3dpathfinding.homeunix.org/%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://3dpathfinding.homeunix.org/%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://3dpathfinding.homeunix.org/ }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} Technische Universität München, Daniel Kastenholz, 2006: „3D Pathfinding“</ref>

Verschiedene Algorithmen sind in der freien Python-Bibliothek NetworkX implementiert.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:|{{#if:Algorithms - Shortest Paths|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Algorithms - Shortest Paths}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Algorithms - Shortest Paths}}}}|[{{#invoke:URLutil|getNormalized|1=https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Algorithms - Shortest Paths}}}}]}}{{#if:| ({{{format}}}{{#if:NetworkX 2.2 documentation{{#if: 2018-10-24 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}

          | )
          | {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html}}%7C%7C URL ungültig}}}}{{#if:Algorithms - Shortest Paths|{{#if:{{#invoke:WLink|isValidLinktext|1=Algorithms - Shortest Paths|lines=0}}|| Linktext ungültig}}}}{{#if: NetworkX 2.2 documentation| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=NetworkX 2.2 documentation}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2018-10-24 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2018-10-24 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2018-10-24 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}|{{{archiv-datum}}}{{#if:497659||(?)}}}}}}{{#if: 2018-10-24|;}}}}{{#if: 2018-10-24| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2018-10-24 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2018-10-24|class=Zitationswartung}} }} {{#invoke:DateTime|format|2018-10-24|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:NetworkX 2.2 documentation{{#if: 2018-10-24 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:en|en|de}}|de||
          {{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2018-10-24 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if:

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}}

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html
      | {{#if:{{#invoke:URLutil|isWebURL|https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html
       | {{#if:{{#invoke:URLutil|isWebURL|https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html
      | {{#if:{{#invoke:URLutil|isWebURL|https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html
       | {{#if:{{#invoke:URLutil|isWebURL|https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}} {{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>

Siehe auch

Route

Einzelnachweise