Merge remote-tracking branch 'upstream/master'

3 files changed, 65 insertions, 13 deletions

diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex
index 8994066..4a450f1 100644
--- a/buch/papers/verkehr/section1.tex
+++ b/buch/papers/verkehr/section1.tex
@@ -1,55 +1,87 @@
 \label{section:verkehr/einfuehrung}
 
 Das Verkehrsnetz besteht aus allen Anlagen, auf oder unter der Erdoberfläche, auf denen eine räumliche Fortbewegung von Personen oder auch Gütern stattfindet. Verkehrsnetze sind ein Bestandteil der Verkehrsinfrastruktur, die auf topografischen Karten festgehalten werden. Sie umfassen den Schienenverkehr, alle Strassen und Wege, wie auch Flugplätze und alle dazugehörigen Bauwerke.
+\index{Verkehrsnetz}%
+\index{Fortbewegung}%
+\index{topographische Karte}%
+\index{Flugplatz}%
 Aus verkehrsgeografischer Sicht besteht das Verkehrsnetz aus Kanten, Knotenpunkten und dem Hinterland. Die Knotenpunkte werden auch hier durch die Kanten verbunden, die den Verkehrsstrom aufnehmen, wobei das Hinterland durch einzelne Knoten versorgt wird. Die Aufteilung in Kanten und Knotenpunkte ermöglicht eine Vereinfachung komplexer Verkehrsnetze, damit sie mittels der Graphentheorie untersucht werden können.
+\index{Knotenpunkt}%
+\index{Hinterland}%
+\index{Verkehrtsstrom}%
 Grundsätzlich können kurze Wege zwischen den Knotenpunkten das Ziel beim Aufbau eines Verkehrsnetzes sein. Es kann aber auch versucht werden, die Bau- und Unterhaltskosten des Verkehrsnetzes in einem gewissen Rahmen zu halten. Aus diesen Vorgaben ergibt sich dann, je nach dem was gewünscht wird, eine grob- oder feinmaschige Struktur des Netzes.
+\index{Graphentheorie}%
 Ziel ist aber ein möglichst wirtschaftliches und optimales Verkehrsnetz.
 
 \section{Suchalgorithmen}
 Inbesondere bei Graphen in Form von Verkehrsnetzen ist das Finden eines kürzesten Weges von Interesse. Mathematisch betrachtet handelt es sich hierbei um ein Optimierungsproblem, bei dem die Summe der Kantengewichte zwischen zwei Knoten minimiert werden soll. Zu diesem Zweck existieren verschiedene Suchalgorithmen. In den folgenden Abschnitten wird auf eine Auswahl davon eingegangen. Zuvor ist es jedoch notwendig, einige Begriffe und Eigenschaften von Suchalgorithmen zu definieren.
+\index{kürzester Weg}%
+\index{Optimierungsproblem}%
+\index{Suchalgorithmus}%
 
 Einerseits wird zwischen optimalen und nicht-optimalen Algorithmen unterschieden. Ein Suchalgorithmus gilt als optimal, falls er einen günstigsten Pfad zwischen zwei Knoten findet. Es gilt zu beachten, dass im Falle des Vorhandenseins von mehrerern Pfaden mit identischer, minimaler Summe der Kantengewichte zwischen zwei Knoten, mindestens einer dieser Pfade gefunden wird.
+\index{optimaler Algorithmus}%
+\index{Algorithmus, optimal}%
 
 Weiter wird zwischen informierten und uninformierten Algorithmen differenziert. Während uninformierte Suchalgorithmen den Suchraum schematisch auf Basis der Eigenschaften des Graphen absuchen, bis eine günstigste Lösung gefunden wurde, verwenden informierte Suchalgorithmen eine Heuristik zur Abschätzung der Suchrichtung. Oftmals wird bei informierten Algorithmen ein Verlust der Optimalität zugunsten einer verbesserten Rechenzeit in Kauf genommen. Es exisitieren jedoch auch Heurstiken, die eine optimale Lösung gewährleisten.
+\index{Heuristik}%
+\index{informierter Algorithmus}%
+\index{Algorithmus, informiert}%
 
+\index{Greedy-Algorithmus}%
+\index{gieriger Algorithmus}%
+\index{Algorithmus, gierig}%
 Eine besondere Art von Suchalgorithmen stellen die sogenannten Greedy-Algorithmen, zu deutsch gierige Algorithmen, dar. Sie zeichnen sich dadurch aus, dass sie stets den zurzeit günstigsten Folgezustand auswählen. Dadurch sind sie in der Regel äusserst effizient, garantieren bei vielen Problemstellungen jedoch keine optimale Lösung.
 
 \subsection{Dijkstra-Algorithmus}
 Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Informatikprofessor Edsger Dijkstra. Er gehört zur Klasse der uninformierten Greedy-Algorithmen. Zudem ist die Optimalität bei strikt positiven Kantengewichten gewährleistet.
+\index{Dijkstra, Edsger}%
+\index{Dijkstra-Algorithmus}%
 Vorteilhaft ist die einfache Implementierung. Abhängig von der Programmiersprache sind zwischen 30 und 40 Zeilen an Code ausreichend, damit er den kürzesten Pfad zwischen einem Startknoten $a$ und Zielknoten $b$ finden kann. 
 
 Die für dieses Paper verwendete programmierte Funktion (MATLAB) verwendet eine abgewandelte Form der gewichteten Adjazenz-Matrix $A$, für welche gilt:
+\index{Matlab}%
+\index{Adjazenz-Matrix}%
 Der Matrix-Eintrag $A_{i,j}$ enthält das Kantengewicht der Kante von Knoten $j$ nach $i$ auf. Falls keine Kante zwischen $j$ und $i$ vorhanden ist, beträgt der Eintrag $\infty$. Dies vereinfacht die Implementierung zur Bestimmung des nächst-günstigsten Pfades.
 Zudem werden zwei Hilfs-Vektoren $\vec{d}$ und $\vec{b}$ der Länge $n$ eingeführt, wobei $n$ die Anzahl Knoten des Graphen ist. Im Vektoreintrag $\vec{d}(i)$ wird das kummulierte Kantengewicht zur Erreichung von Knoten $i$ vom Startknoten $a$ gespeichert. Der Eintrag $\vec{d}(a)$ beträgt somit $0$. Im Vektor $\vec{b}$ wird zudem vermerkt, falls ein Knoten bereits als Ziel eines kürzesten Pfads gefunden wurde und somit für die weitere Suche nicht mehr berücksichtigt werden muss ($\vec{b}(i)=1$, sonst $\vec{b}(i)=0$).
 
-Ausgehend vom Startknoten $a$ wird nun anhand der Matrix $A$ in der Spalte $a$ nach dem kleinsten Eintrag gesucht. Somit wird der Folgeknoten $c$ gefunden. Dieser Vorgang wird nun wiederholt, wobei jedoch sämtliche von Knoten $a$ und $c$ erreichbaren Knoten berücksichtigt werden, die noch nicht besucht wurden. In anderen Worten alle nicht verschwindenden Einträge $i$ der Spalten $a$ und $c$ der Matrix $A$, für welche gilt $\vec{b}(i)=0$. Ausschlaggebend für die folgende Auswahl ist die Summe der kummulierten Kantengewichte und des Kantengewichts des nächsten Knotens. Als Beispiel zur Erreichung von Knoten $k$ über Knoten $j$:
+Ausgehend vom Startknoten $a$ wird nun anhand der Matrix $A$ in der Spalte $a$ nach dem kleinsten Eintrag gesucht. So wird der Folgeknoten $c$ gefunden. Dieser Vorgang wird nun wiederholt, wobei jedoch sämtliche von Knoten $a$ und $c$ erreichbaren Knoten berücksichtigt werden, die noch nicht besucht wurden. In anderen Worten alle nicht verschwindenden Einträge $i$ der Spalten $a$ und $c$ der Matrix $A$, für welche gilt $\vec{b}(i)=0$. Ausschlaggebend für die folgende Auswahl ist die Summe der kummulierten Kantengewichte und des Kantengewichts des nächsten Knotens. Als Beispiel zur Erreichung von Knoten $k$ über Knoten $j$:
 \begin{equation}
-\vec{d}(k)=\vec{d}(j)+A(k,j)
+\vec{d}(k)=\vec{d}(j)+A(k,j).
 \end{equation}
 Diese Iteration wird solange durchgeführt, bis der Folgeknoten dem Zielknoten entspricht.
 
 \subsection{A*-Algorithmus}
 Der A*-Algorithmus basiert auf dem Dijkstra-Algorithmus, verwendet jedoch eine Heuristik zur Abschätzung der günstigsten Suchrichtung. Somit handelt es sich um einen informierten Greedy-Algorithmus, der abhängig von der verwendeten Heuristik auch optimal sein kann. Er wurde von Peter Hart, Nils Nilsson und Bertram Raphael entwickelt.
+\index{Hart, Peter}%
+\index{Nilsson, Nils}%
+\index{Raphel, Bertram}%
+\index{A*-Algorithmus}%
 
 \subsection{Anwendung A*-Algorithmus}
 Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus von Dijkstra. Gemäss dem Algorihtmus von Dijkstra werden von einem Startknoten aus die jeweiligen Nachbarknoten, die Nachbarknoten der Nachbarknoten usw. verarbeitet. Die Kantengewichte werden dabei aufsummiert und die Priorität wird auf die Kante gelegt, die das geringste Gewicht aufweist. Mit diesem Verfahren wird sichergestellt, dass die erste gefundene Lösung auch eine optimale Lösung darstellt.\\
+\index{Shortest-Path-Algorithmus}%
 
-Der A*-Algorithmus unterscheidet sich vom Dijkstra-Algorithmus dahingehend, dass bei der Auswahl des Folgeknotens, nicht nur die Summe der Kantengewichte $\vec{d}(j)+A(k,j)$, sondern zusätzlich die für jeden Knoten definierte Abschätzfunktion $f(k)$ hinzuaddiert wird. Dies passiert jedoch nur bei der \emph{Auswahl} des Folgeknotens. Der Wert von $f(k)$ wird nicht im Eintrag $\vec{d}(k)$ gespeichert. Somit wird gewährleistet, dass der gefundene Pfad, der Summe der Kantengewichte entspricht. Ein Beispiel dafür, wie eine Abschätzfunktion gebildet werden kann findet sich in Abschnitt \ref{sec:verkehr/euklidische}
+Der A*-Algorithmus unterscheidet sich vom Dijkstra-Algorithmus dahingehend, dass bei der Auswahl des Folgeknotens, nicht nur die Summe der Kantengewichte $\vec{d}(j)+A(k,j)$, sondern zusätzlich die für jeden Knoten definierte Abschätzfunktion $f(k)$ hinzuaddiert wird. Dies passiert jedoch nur bei der \emph{Auswahl} des Folgeknotens. Der Wert von $f(k)$ wird nicht im Eintrag $\vec{d}(k)$ gespeichert. Somit wird gewährleistet, dass der gefundene Pfad, der Summe der Kantengewichte entspricht. Ein Beispiel dafür, wie eine Abschätzfunktion gebildet werden kann, findet sich in Abschnitt \ref{sec:verkehr/euklidische}
 
 \subsection{Euklidische Heuristik}
 \label{sec:verkehr/euklidische}
-Bei Verkehrsnetzen ist die euklidische Distanz eine gängige und zuverlässige Heurstik. Dabei wird zu den effektiven Reisekosten zum aktuellen Knoten die euklidische Distanz bis zum Zielknoten hinzuaddiert. Dadurch wird die Kostenfunktion konsequent nie überschätzt. Dies stellt eine Voraussetzung an eine zulässige Heuristik dar. Unter Verwendung dieser Heuristik gilt der A*-Algorithmus als optimal.
+Bei Verkehrsnetzen ist die euklidische Distanz eine gängige und zuverlässige Heuristik. Dabei wird zu den effektiven Reisekosten zum aktuellen Knoten die euklidische Distanz bis zum Zielknoten hinzuaddiert. Dadurch wird die Kostenfunktion konsequent nie überschätzt. Dies stellt eine Voraussetzung an eine zulässige Heuristik dar. Unter Verwendung dieser Heuristik gilt der A*-Algorithmus als optimal.
 
-Bei der euklidischen Heuristik wird die Abschätzfunktion $f(k)$ für jeden Knoten $k$ durch euklidische Distanz zum Zielknoten $b$ gebildet.
+Bei der euklidischen Heuristik wird die Abschätzfunktion $f(k)$ für jeden Knoten $k$ durch euklidische Distanz
 \begin{equation}
 f(k)=\sqrt{(x_k-x_b)^2+(y_k-y_b)^2}
 \end{equation}
+zum Zielknoten $b$ gebildet.
 
 Was bei einem physischen Verkehrsnetz einfach zu bewältigen ist, da Koordinaten von Verkehrsnetzen zur Berechnung der Distanz verwendet werden können, ist bei virtuellen Netzwerken (z.B. Servernetzen) entweder nicht möglich, oder nicht relevant. Hier können hingegen andere Eigenschaften des Netzwerks verwendet werden, auf welche in diesem Paper nicht weiter eingegangen wird.
 
 \subsection{Floyd-Warshall-Algorithmus}
+\index{Floyd-Warshall-Algorithmus}%
 Der Floyd-Warshall-Algorithmus, auch Tripel-Algorithmus genannt, wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt.
-Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die günstigsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algrithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph keinen negativen Kreis (Zyklus) aufweist. Ein Kreis, sprich ein Weg mit identischem Start- und Zielknoten, ist negativ, falls die Summe der Kantengewichte des Weges kleiner als null ist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis.
+Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die günstigsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algorithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph keinen negativen Kreis (Zyklus) aufweist. Ein Kreis, sprich ein Weg mit identischem Start- und Zielknoten, ist negativ, falls die Summe der Kantengewichte des Weges kleiner als null ist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis.
+\index{Zyklus}%
+\index{Kreis (Graphentheorie)}%
 
 \subsection{Anwendung Floyd-Warshall-Algorithmus}
 
@@ -66,6 +98,9 @@ ermittelt.
 
 
 \section{PageRank-Algorithmus}
+\index{PageRank-Algorithmus}%
+\index{Page, Larry}%
+\index{Brin, Sergey}%
 Der PageRank-Algorithmus wurde von den Gründern von Google, Larry Page und Sergey Brin im Jahr 1996 entwickelt und zum Patent angemeldet. Zwei Jahre später gründeten sie ihr Unternehmen Google Inc.
 Beim PageRank-Algorithmus handelt es sich nicht um einen Suchalgorithmus, stattdessen werden Knoten aufgrund der Vernetzung des vorliegenden Graphen bewertet.
 Verwendet wird er beispielsweise um die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur zu bewerten und relevante Suchergebnisse zu ermittteln. Der PageRank wird umso höher, je mehr hochwertige Links auf eine Webseite verweisen und je höher die Gewichtung einer Webseite ist, desto grösser ist der Effekt.
@@ -84,10 +119,15 @@ Grundsätzlich setzt sich der PageRank Algorithmus mit der Fragestellung auseina
 
 
 
-Für ungerichtete Graphen mit $n$ Knoten gilt \begin{equation}A_{i,j}=A_{j,i}\end{equation} und weiter \begin{equation}A_{i,i}=0\quad\forall i\in \left\{1\dots n\right\}\end{equation}
+Für ungerichtete Graphen mit $n$ Knoten gilt \begin{equation}A_{i,j}=A_{j,i}\end{equation} und weiter
+\begin{equation}
+A_{i,i}=0\quad\forall i\in \left\{1\dots n\right\}.
+\end{equation}
 Beim PageRank-Algorithmus wird eine abgewandelte Form der Adjazenz-Matrix verwendet.
 Dabei werden die Matrix-Einträge spaltenweise durch die jeweilige Spaltensumme geteilt, so entsteht die Link-Matrix
-\[ P_{i,j}=\frac{A_{i,j}}{\sum_{k=1}^{n}A_{k,j}} \]
+\[
+P_{i,j}=\frac{A_{i,j}}{\sum_{k=1}^{n}A_{k,j}}.
+\]
 Anschliessend multipliziert man diese Matrix $P$ mit einem Spaltenvektor $\Vec{r_0}$ mit $n$ Einträgen, für welchen gilt:
 \( \Vec{r_0}(i) = \frac{1}{n} \quad\forall i\in \left\{1\dots n\right\} \)
 Dieser Vektor stellt ein neutrales Ranking dar. Alle Knoten werden gleich gewichtet.
@@ -95,4 +135,4 @@ Dadurch erhält man wiederum einen $n$-zeiligen Spaltenvektor $\Vec{r_1}$, der d
 \( \Vec{r_2} = P\cdot\Vec{r_1} = P\cdot(P\cdot\Vec{r_0}) = P^2\cdot\Vec{r_0}\)
 und somit allgemein:
 \( \Vec{r_i} = P^i\cdot\Vec{r_0}\)
-Der Vektor $\Vec{r_i}$ konvergiert zu einem Eigenvektor von $P$ der das abschliessende Ranking darstellt.
+Der Vektor $\Vec{r_i}$ konvergiert zu einem Eigenvektor von $P$, der das abschliessende Ranking darstellt.
diff --git a/buch/papers/verkehr/section2.tex b/buch/papers/verkehr/section2.tex
index 527885e..a0e88b6 100644
--- a/buch/papers/verkehr/section2.tex
+++ b/buch/papers/verkehr/section2.tex
@@ -4,6 +4,7 @@
 Um zwei der vorgestellten Suchalgorithmen zu vergleichen, wurden zwei Versuchsreihen erstellt. Dazu wurden in einem ersten Schritt zufällige Netzwerke generiert und anschliessend der Dijkstra- und der A*-Algorithmus auf das Netzwerk angewandt.
 Dieser Vorgang wurde für die zufällig generierten Netzwerke mit einer Knotenzahl von 10, 20 50, 100, 200, 500 und 1000 je zehnmal wiederholt.
 Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(|E|\log{}|V|)$ auf, wobei $E$ die Menge der Kanten (engl. \emph{edges}) und $V$ die Menge der Knoten (engl. \emph{vertices}) des Graphen $G$ darstellt.
+\index{Zeitkomplexität}%
 Für den A*-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine definitive Angabe zur Zeitkomplexität machen.
 
 Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind.
diff --git a/buch/papers/verkehr/section3.tex b/buch/papers/verkehr/section3.tex
index 9aa8ae4..50bae2a 100644
--- a/buch/papers/verkehr/section3.tex
+++ b/buch/papers/verkehr/section3.tex
@@ -1,9 +1,20 @@
 \section{Ausblick}
 \subsection{Optimierungsprobleme bei Graphen}
-Das Finden eines kürzesten Pfades, sprich die Minimierung der Summe der Kantengewichte, ist nur eines der Optimierungsprobleme, die sich im Bereich von Graphen aufstellen lassen. Verschiedene, ähnliche Problemstellungen lassen sich teilweise mit denselben Algorithmen lösen.
+Das Finden eines kürzesten Pfades, sprich die Minimierung der Summe der Kantengewichte, ist nur eines der Optimierungsprobleme, die sich im Bereich von Graphen aufstellen lassen.
+Verschiedene, ähnliche Problemstellungen lassen sich teilweise mit denselben Algorithmen lösen.
 
-Im Bereich vom Computernetzwerken könnte zum Beispiel die Minimierung der Knotenzahl zur Datenübbertragung von Interesse sein. Dabei lässt sich dieses Problem einfach dadurch lösen, dass dem Dijkstra- oder dem A*-Algorithmus anstelle der gewichteten Adjazenz-Matrix (mit Kantengewichten als Einträgen) die ungewichtet Adjazenz-Matrix als Argument übergeben wird. Der gefundene kürzeste Pfad enstpricht der Anzahl benutzter Kanten, bzw. der Anzahl besuchter Knoten.  
+Im Bereich vom Computernetzwerken könnte zum Beispiel die Minimierung der Knotenzahl zur Datenübbertragung von Interesse sein.
+Dabei lässt sich dieses Problem einfach dadurch lösen, dass dem Dijkstra- oder dem A*-Algorithmus anstelle der gewichteten Adjazenz-Matrix (mit Kantengewichten als Einträgen) die ungewichtet Adjazenz-Matrix als Argument übergeben wird.
+Der gefundene kürzeste Pfad enstpricht der Anzahl benutzter Kanten, bzw. der Anzahl besuchter Knoten.  
 
 \subsection{Wahl der Heuristik}
-Ein grundlegendes Problem bei der Anwendung des A* oder ähnlicher informierter Suchalgorithmen ist die Wahl der Heurstik. Bei einem physischen Verkehrsnetz kann bspw. die euklidische Distanz problems ermittelt werde. Bei einem regionalen Netzwerk ist die Annahme eines orthogonalen X-Y-Koordinatenetzes absolut ausreichend. Dies gilt z.B. auch für das Vernessungsnetz der Schweiz\footnote{Die aktuelle Schweizer Referenzsystem LV95 benutzt ein E/N-Koordinatennetz, wobei aufgrund zunehmender Abweichung vom Referenzellipsoid bei grosser Entfernung vom Nullpunkt ein Korrekturfaktor für die Höhe angebracht werden muss.} Bei überregionalen Netzwerken (Beispiel: Flugverbindungen) ist hingegen eine Berechnung im dreidimensionalen Raum, oder vereinfacht als Projektion auf das Geoid notwendig. Anonsten ist der Ablauf bei der Ausführung des Algorithmus allerdings identisch.
-In nicht-physischen Netzwerken stellt sich jedoch eine zweite Problematik. Da eine physische Distanz entweder nicht ermittelt werden kann, oder aber nicht ausschlaggebend ist, sind andere Netzwerk-Eigenschaften zur Beurteilung beizuziehen. Die Zuverlässigkeit ist dabei aber in den meisten Fällen nicht vergleichbar hoch, wie bei der euklidischen Heuristik. Oftmals werden deshalb bei derartigen Problem auch Algorithmen angewendet, die eine deutlich optimierte Zeitkomplexität aufweisen, dafür aber nicht mit Sicherheit den effizienstesten Pfad finden.
+Ein grundlegendes Problem bei der Anwendung des A* oder ähnlicher informierter Suchalgorithmen ist die Wahl der Heurstik.
+Bei einem physischen Verkehrsnetz kann bspw.~die euklidische Distanz problems ermittelt werde.
+Bei einem regionalen Netzwerk ist die Annahme eines orthogonalen X-Y-Koordinatenetzes absolut ausreichend.
+Dies gilt z.~B.~auch für das Vernessungsnetz der Schweiz\footnote{Die aktuelle Schweizer Referenzsystem LV95 benutzt ein E/N-Koordinatennetz, wobei aufgrund zunehmender Abweichung vom Referenzellipsoid bei grosser Entfernung vom Nullpunkt ein Korrekturfaktor für die Höhe angebracht werden muss.}.
+Bei überregionalen Netzwerken (Beispiel: Flugverbindungen) ist hingegen eine Berechnung im dreidimensionalen Raum, oder vereinfacht als Projektion auf das Geoid notwendig.
+Ansonsten ist der Ablauf bei der Ausführung des Algorithmus allerdings identisch.
+In nicht-physischen Netzwerken stellt sich jedoch eine zweite Problematik.
+Da eine physische Distanz entweder nicht ermittelt werden kann, oder aber nicht ausschlaggebend ist, sind andere Netzwerk-Eigenschaften zur Beurteilung beizuziehen.
+Die Zuverlässigkeit ist dabei aber in den meisten Fällen nicht vergleichbar hoch, wie bei der euklidischen Heuristik.
+Oftmals werden deshalb bei derartigen Problem auch Algorithmen angewendet, die eine deutlich optimierte Zeitkomplexität aufweisen, dafür aber nicht mit Sicherheit den effizienstesten Pfad finden.