The shortest Path Problem

Das Problem

Man möchte z.B. den kürzeste Pfad von Person A zu B finden. Dabei will man natürlich die Knoten wissen über die Person A gehen muss um Person B zu ereichen. Infos zu dieser Problematik: WikiPedia – Shortest path problem

Performance & Datenbasis

Welcher Algo ist der schnellste? A* soll auch mit einer miesen Heuristik schneller sein als Dijkstra. Der Dijkstra-Algo dürfte eigendlich so schnell sein wie ein A* Algo ohne Heuristik, weil der Dijkstra-Algorithmus eigendlich ein A*-Algorithmus ohne Heuristik ist.

Dijkstra O(n²) mit Fibonacci-Heaps
Dijkstra O(n * log(n) + m) laut wiki ???
Dijkstra O( (n+m) * log(n) ) mit binären oder binomialen Heap

Ameisenalgorithmus: O(4,4 * 10^n) 
A*: g'(n)=1+alpha*(g(n)-1)     f(n) = g(n) + h(n)
Dijkstra: O(m*lg(n))
Bellman-Ford: O(n+m)
Floyd-Warshall: O(n^3)

Ameisenalgorithmus: O(4,4 * 10^n)

A*: g'(n)=1+alpha*(g(n)-1) f(n) = g(n) + h(n)

Dijkstra: O(m*lg(n))

Bellman-Ford: O(n+m)

Floyd-Warshall: O(n^3)

n= Anzahl Knoten, m= Anzahl Kanten im Graph

Datenstrukturen

– Unsorted arrays or linked lists
– Sorted arrays
– Sorted linked lists
– Sorted skip lists
– Indexed arrays
– Hash tables
– Binary heaps
– Splay trees
– Splay trees
– HOT queues – Heap On Top queues
– Comparison
– Hybrid representations

Datenmenge

Beim Floyd-Warshall-Algorithmus sind Arrays eine gute wahl. Er braucht allerdings sehr viel Speicherplatz für die Grunddatenmenge. Bei einer Feldgröße von 20×20 und einer quadratischen Matrix von Floats benötigt man über 600MB RAM

Weblinks zu Datenmengen

Lösungen mit Codefragmenten

slashster – PHP / Mysql Friend of a Friend implementation (e.g: Orkut, Friendster)
Javascript implementierung
Einige Infos zur Lösung mit MySQL

Die verschiedenen Algorithmen

Einige Algorithmen bieten die Lösung. Das sind z.B. die folgenden:

A*-Algorithmus – Wikipedia
Dijkstra-Algorithmus – Wikipedia
Floyd-Warshall-Algorithmus – Wikipedia
Ameisenalgorithmus – ameisenalgorithmus.de – auf Wikipedia
Bellman-Ford-Algorithmus – Wikipedia
Best-First-Search (BFS) algorithm
Fibonacci-Heap – Wikipedia
Johnson-Algorithmus
Roy-Floyd

A*-Algorithmus

A* PHP Beispiel
PAn
Amit’s A* Pages – brauchbare infos zu Heuristik beim A* Algo
F-A-pathfinding-in-PHP

Dijkstra-Algorithmus

Der Dijkstra-Algorithmus ist ein A*-Algorithmus ohne Heuristik

Dijkstra’s algorithm WIKI
Dijkstra-s-Algorithm-Shortes-Path – Codesnippet für C, C#, C++, ActionScript, PHP, Python, Visual Basic 6
Building Web Comunities – Kapitel: Djikstra’s Algorithm
Dijkstra Pathfinding Algorithmus optimieren?
Dijkstra-Algorithmus unter Verwendung eines Fibonacci-Heaps
Dijkstra’s Algorithm – Erklärung bei verschiedenen Datenstrukturen als Q

PHP Lösungen

phpclasses.org package 5248 – PHP Lösung
Dijkstra – noch eine PHP Lösung
codeguru.com – PHP Lösung

Datenbank Lösungen

Dijkstra’s shortest path algorithm – SQL Implemetierungen

Floyd-Warshall Agorithmus

wiki – Algorithmus von Floyd und Warshall