最短路Shortest-Path

Algorithm: Dijkstra

Given a graph $G$, an total-order $\le$ on the set of the weight of all path $|AB|$ (AB can be same) and a binary operator $+$, then the weight of a path (the sum of all edges on the path, denotes $|AB|$) must satisfying a property (a bit like triangular inequality, but not same):

• If $|AB|\le |AC|$, then $|AB|\le |AC|+|CB|$ ($ABC$ maybe the same)

Then, Dijkstra is used to calculate the least-element under the order $\le$ of the weight $|SX|$ where $S$ is a start-point, $X$ is a any point.

There are some examples:

• A graph (may contains loop (self-loop or non-self-loop)) with all edges $\ge 0$, the weight of a path is the sum of all edges on it and given a start-point $S$, calculate the minimal-distance of $|SX|$ (X is an arbitrary point)
  Defining the Dijkstra-Order $\le (a,b)=a\le b$, Dijkstra-Add $+(a,b)=a+b$
  Then, we can found this satisfies the Dijkstra-Triangular-Inequality

• A graph (may contains loop (self-loop or non-self-loop)) with all edges $\le 0$, the weight of a path is the sum of all edges on it and given a start-point $S$, calculate the maximal-distance of $|SX|$ (X is an arbitrary point)
  Defining the Dijkstra-Order $\le (a,b)=a\ge b$ (notice here), Dijkstra-Add $+(a,b)=a+b$
  Then, we can found this satisfies the Dijkstra-Triangular-Inequality

• A graph (may contains loop (self-loop or non-self-loop)) with all edges be any real-number in $[0,1]$, the weight of a path is the product of all edges on it and given a start-point $S$, calculate the maximal-distance of $|SX|$ (X is an arbitrary point)
  Defining the Dijkstra-Order $\le (a,b)=a\ge b$ (notice here), Dijkstra-Add $+(a,b)=a\ast b$
  Then, we can found this satisfies the Dijkstra-Triangular-Inequality