@MISC{GRAPH_5.MIZ,
  AUTHOR = {Chen, Jing-Chao and Nakamura, Yatsuka},
  TITLE = {The Underlying Principle of {D}ijkstra's Shortest Path Algorithm},
  SECTION1 = {Preliminaries},
  SECTION2 = {Additional Properties of Finite Sequences},
  SECTION3 = {Additional Properties of Chains and Oriented Paths},
  SECTION4 = {Additional Properties of Acyclic Oriented Paths},
  SECTION5 = {The Set of the Vertices On a Path or an Edge},
  SECTION6 = {Directed Paths between Two Vertices},
  SECTION7 = {Acyclic (or Simple) Paths},
  SECTION8 = {Weight Graphs and Their Basic Properties},
  SECTION9 = {Shortest Paths and Their Basic Properties},
  SECTION10 = {Basic Properties of a Graph with Finite Vertices},
  SECTION11 = {Three Basic Theorems for Dijkstra's Shortest Path Algorithm},
  DAY = {07},
  MONTH = {January},
  YEAR = {2003},
  ADDRESS1 = {Donghua University\\Shanghai},
  ADDRESS2 = {Shinshu University\\Nagano},
  SUMMARY = {A path from a source vertex $v$ to a target vertex $u$ is said to
    be a shortest path if its total cost is minimum among all $v$-to-$u$ paths.
    Dijkstra's algorithm is a classic shortest path algorithm, which
    is described in many textbooks. To justify its correctness (whose
    rigorous proof will be given in the next article), it is necessary
    to clarify its underlying principle. For this purpose, the article
    justifies the following basic facts, which are the core of Dijkstra's
    algorithm.
  \begin{itemize}
  \itemsep-3pt
  \item A graph is given, its vertex set is denoted by $V.$ Assume $U$
      is the subset of $V,$ and if a path $p$ from $s$ to $t$ is
      the shortest among the set of paths, each of which passes
      through only the vertices in $U,$
      except the source and sink, and its source and sink is $s$ and in $V,$
      respectively, then $p$ is a shortest path from $s$ to $t$ in the graph,
      and for any subgraph which contains at least $U,$ it is also the
      shortest.
  \item Let $p(s,x,U)$ denote the shortest path from $s$ to $x$ in a subgraph
      whose the vertex set is the union of $\{s,x\}$ and $U,$ and cost $(p)$
      denote the cost of path $p(s,x,U),$ cost$(x,y)$ the cost of the edge
      from $x$ to $y.$ Give $p(s,x,U),$ $q(s,y,U)$ and $r(s,y,U \cup \{x\})$.
      If ${\rm cost}(p) = {\rm min} \{{\rm cost}(w):
      w(s,t,U) \wedge t \in V\}$,
      then we have $${\rm cost}(r) = {\rm min}
      ({\rm cost}(p)+{\rm cost}(x,y),{\rm cost}(q)).$$
      \end{itemize}
      \noindent This is the well-known triangle comparison of Dijkstra's algorithm.}}

