/usr/share/doc/postgresql-9.5-pgrouting-doc/html/en/src/dijkstra/doc/index.html is in postgresql-9.5-pgrouting-doc 2.1.0-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>pgr_dijkstra - Shortest Path Dijkstra — pgRouting Manual (2.1.0)</title>
<link rel="stylesheet" href="../../../_static/haiku.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '../../../',
VERSION: '2.1.0 (b38118a master)',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="../../../_static/jquery.js"></script>
<script type="text/javascript" src="../../../_static/underscore.js"></script>
<script type="text/javascript" src="../../../_static/doctools.js"></script>
<script type="text/javascript" src="../../../_static/mathjax/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<link rel="shortcut icon" href="../../../_static/favicon.ico"/>
<link rel="top" title="pgRouting Manual (2.1.0)" href="../../../doc/index.html" />
<link rel="up" title="Routing Functions" href="../../index.html" />
<link rel="next" title="pgr_dijkstra (V 2.0)- Shortest Path Dijkstra" href="dijkstra_v2.html" />
<link rel="prev" title="pgr_bdDijkstra - Bi-directional Dijkstra Shortest Path" href="../../bd_dijkstra/doc/index.html" />
</head>
<body role="document">
<div class="header" role="banner"><img class="rightlogo" src="../../../_static/pgrouting.png" alt="Logo"/><h1 class="heading"><a href="../../../index.html">
<span>pgRouting Manual (2.1.0)</span></a></h1>
<h2 class="heading"><span>pgr_dijkstra - Shortest Path Dijkstra</span></h2>
</div>
<div class="topnav" role="navigation" aria-label="top navigation">
<p>
«  <a href="../../bd_dijkstra/doc/index.html">pgr_bdDijkstra - Bi-directional Dijkstra Shortest Path</a>
  ::  
<a class="uplink" href="../../../doc/index.html">Contents</a>
  ::  
<a href="dijkstra_v2.html">pgr_dijkstra (V 2.0)- Shortest Path Dijkstra</a>  »
</p>
</div>
<div class="content">
<div class="section" id="pgr-dijkstra-shortest-path-dijkstra">
<span id="pgr-dijkstra"></span><h1>pgr_dijkstra - Shortest Path Dijkstra<a class="headerlink" href="#pgr-dijkstra-shortest-path-dijkstra" title="Permalink to this headline">¶</a></h1>
<div class="section" id="version-2-0-deprecated">
<h2>Version 2.0 (deprecated)<a class="headerlink" href="#version-2-0-deprecated" title="Permalink to this headline">¶</a></h2>
<blockquote>
<div><ul class="simple">
<li><a class="reference internal" href="dijkstra_v2.html#pgr-dijkstra-v2"><span>pgr_dijkstra</span></a> - Shortest Path Dijkstra</li>
</ul>
</div></blockquote>
</div>
<div class="section" id="version-2-1">
<h2>Version 2.1<a class="headerlink" href="#version-2-1" title="Permalink to this headline">¶</a></h2>
<blockquote>
<div><ul class="simple">
<li><a class="reference internal" href="dijkstra_v3.html#pgr-dijkstra-v3"><span>pgr_dijkstra</span></a> - Shortest Path Dijkstra</li>
</ul>
</div></blockquote>
</div>
</div>
<div class="section" id="the-problem-definition">
<h1>The problem definition<a class="headerlink" href="#the-problem-definition" title="Permalink to this headline">¶</a></h1>
<p>Given the following query:</p>
<p>pgr_dijkstra(<span class="math">\(sql, start_{vid}, end_{vid}, directed\)</span>)</p>
<p>where <span class="math">\(sql = \{(id_i, source_i, target_i, cost_i, reverse\_cost_i)\}\)</span></p>
<p>and</p>
<blockquote>
<div><ul class="simple">
<li><span class="math">\(source = \bigcup source_i\)</span>,</li>
<li><span class="math">\(target = \bigcup target_i\)</span>,</li>
</ul>
</div></blockquote>
<p>The graphs are defined as follows:</p>
<p class="rubric">Directed graph</p>
<p>The weighted directed graph, <span class="math">\(G_d(V,E)\)</span>, is definied by:</p>
<ul class="simple">
<li>the set of vertices <span class="math">\(V\)</span><ul>
<li><span class="math">\(V = source \cup target \cup {start_{vid}} \cup {end_{vid}}\)</span></li>
</ul>
</li>
<li>the set of edges <span class="math">\(E\)</span><ul>
<li><span class="math">\(E = \begin{cases} &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} &\quad \text{ if } reverse\_cost = \varnothing \\ \\ &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} &\quad \text{ if } reverse\_cost \neq \varnothing \\ \end{cases}\)</span></li>
</ul>
</li>
</ul>
<p class="rubric">Undirected graph</p>
<p>The weighted undirected graph, <span class="math">\(G_u(V,E)\)</span>, is definied by:</p>
<ul class="simple">
<li>the set of vertices <span class="math">\(V\)</span><ul>
<li><span class="math">\(V = source \cup target \cup {start_v{vid}} \cup {end_{vid}}\)</span></li>
</ul>
</li>
<li>the set of edges <span class="math">\(E\)</span><ul>
<li><span class="math">\(E = \begin{cases} &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} &\quad \text{ if } reverse\_cost = \varnothing \\ \\ &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} \\ \cup &\{(source_i, target_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} &\quad \text{ if } reverse\_cost \neq \varnothing \\ \end{cases}\)</span></li>
</ul>
</li>
</ul>
<p class="rubric">The problem</p>
<p>Given:</p>
<blockquote>
<div><ul class="simple">
<li><span class="math">\(start_{vid} \in V\)</span> a starting vertex</li>
<li><span class="math">\(end_{vid} \in V\)</span> an ending vertex</li>
<li><span class="math">\(G(V,E) = \begin{cases} G_d(V,E) &\quad \text{ if } directed = true \\ G_u(V,E) &\quad \text{ if } directed = false \\ \end{cases}\)</span></li>
</ul>
</div></blockquote>
<p>Then:</p>
<div class="math">
\[\begin{split}\text{pgr_dijkstra}(sql, start_{vid}, end_{vid}, directed) =
\begin{cases}
\text{shortest path } \boldsymbol{\pi} \text{ between } start_{vid} \text{and } end_{vid} &\quad \text{if } \exists \boldsymbol{\pi} \\
\varnothing &\quad \text{otherwise} \\
\end{cases}\end{split}\]</div>
<p><span class="math">\(\boldsymbol{\pi} = \{(path_\seq_i, node_i, edge_i, cost_i, agg\_cost_i)\}\)</span></p>
<dl class="docutils">
<dt>where:</dt>
<dd><ul class="first last simple">
<li><span class="math">\(path_\seq_i = i\)</span></li>
<li><span class="math">\(path_\seq_{| \pi |} = | \pi |\)</span></li>
<li><span class="math">\(node_i \in V\)</span></li>
<li><span class="math">\(node_1 = start_{vid}\)</span></li>
<li><span class="math">\(node_{| \pi |} = end_{vid}\)</span></li>
<li><span class="math">\(\forall i \neq | \pi |, \quad (node_i, node_{i+1}, cost_i) \in E\)</span></li>
<li><span class="math">\(edge_i = \begin{cases} id_{(node_i, node_{i+1},cost_i)} &\quad \text{when } i \neq | \pi | \\ -1 &\quad \text{when } i = | \pi | \\ \end{cases}\)</span></li>
<li><span class="math">\(cost_i = cost_{(node_i, node_{i+1})}\)</span></li>
<li><span class="math">\(agg\_cost_i = \begin{cases} 0 &\quad \text{when } i = 1 \\ \displaystyle\sum_{k=1}^{i} cost_{(node_{k-1}, node_k)} &\quad \text{when } i \neq 1 \\ \end{cases}\)</span></li>
</ul>
</dd>
<dt>In other words: The algorithm returns a the shortest path between <span class="math">\(start_{vid}\)</span> and <span class="math">\(end_{vid}\)</span> , if it exists, in terms of a sequence of nodes and of edges,</dt>
<dd><ul class="first last simple">
<li><span class="math">\(path_\seq\)</span> indicates the relative position in the path of the <span class="math">\(node\)</span> or <span class="math">\(edge\)</span>.</li>
<li><span class="math">\(cost\)</span> is the cost of the edge to be used to go to the next node.</li>
<li><span class="math">\(agg\_cost\)</span> is the cost from the <span class="math">\(start_{vid}\)</span> up to the node.</li>
</ul>
</dd>
</dl>
<p>If there is no path, the resulting set is empty.</p>
<div class="toctree-wrapper compound">
</div>
</div>
</div>
<div class="bottomnav" role="navigation" aria-label="bottom navigation">
<p>
«  <a href="../../bd_dijkstra/doc/index.html">pgr_bdDijkstra - Bi-directional Dijkstra Shortest Path</a>
  ::  
<a class="uplink" href="../../../doc/index.html">Contents</a>
  ::  
<a href="dijkstra_v2.html">pgr_dijkstra (V 2.0)- Shortest Path Dijkstra</a>  »
</p>
</div>
<div class="footer" role="contentinfo">
© Copyright pgRouting Contributors - Version 2.1.0 (b38118a master).
Last updated on Feb 05, 2016.
Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.3.5.
</div>
</body>
</html>
|