https://svn.boost.org/trac10/ticket/732 <pre class="wiki">Hi, The Johnson's SP algorithm as implemented in the BGL does not easily provide a way to determine whether two vertices are do have a path between them. I include below a simplified version of the example provided with the BGL. Running it I get the output below: D[0][0]=0 D[0][1]=3 D[0][2]=-4 D[1][0]=2147483647 &lt;- no path between nodes '1' and '0' D[1][1]=0 D[1][2]=2147483643 &lt;- no path between nodes '1' and '2' D[2][0]=-2147483645 &lt;- no path between nodes '2' and '0' D[2][1]=-2147483645 &lt;- no path between nodes '2' and '1' D[2][2]=0 That is, there isn't one single value that represents lack of connectivity - one has to pick a value close enough to 'inf' and discriminate with that. Shouldn't 'inf' (however represented) describe lack of connectivity? (To get around this problem, at the moment I run a transitive closure before JSP and use the result of that to determine whether two vertices are connected). Does this make sense or am I missing something? Thanks, Andrea #include &lt;boost/property_map.hpp&gt; #include &lt;boost/graph/adjacency_list.hpp&gt; #include &lt;boost/graph/johnson_all_pairs_shortest.hpp&gt; #include &lt;iostream&gt; int main() { using namespace boost; typedef adjacency_list&lt;vecS, vecS, directedS, no_property, property&lt; edge_weight_t, int, property&lt; edge_weight2_t, int &gt; &gt; &gt; Graph; const int V = 3; typedef std::pair &lt; int, int &gt;Edge; Edge edge_array[] = { Edge(0, 1), Edge(0, 2) }; const std::size_t E = sizeof(edge_array) / sizeof(Edge); Graph g(edge_array, edge_array + E, V); property_map &lt; Graph, edge_weight_t &gt;::type w = get(edge_weight, g); int weights[] = { 3, -4 }; int *wp = weights; graph_traits &lt; Graph &gt;::edge_iterator e, e_end; for (boost::tie(e, e_end) = edges(g); e != e_end; ++e) w[*e] = *wp++; std::vector &lt; int &gt;d(V, (std::numeric_limits &lt; int &gt;::max)()); int D[V][V]; johnson_all_pairs_shortest_paths(g, D, distance_map(&amp;d[0])); std::cout &lt;&lt; " "; std::cout &lt;&lt; std::endl; for (int i = 0; i &lt; V; ++i) for (int j = 0; j &lt; V; ++j) std::cout &lt;&lt; "D[" &lt;&lt; i &lt;&lt; "][" &lt;&lt; j &lt;&lt; "]=" &lt;&lt; D[i][j] &lt;&lt; std::endl; return 0; } </pre> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/732 Trac 1.4.3 Marshall Clow Thu, 12 Jul 2007 15:13:55 GMT https://svn.boost.org/trac10/ticket/732#comment:1 https://svn.boost.org/trac10/ticket/732#comment:1 <ul> <li><strong>owner</strong> changed from <span class="trac-author">Douglas Gregor</span> to <span class="trac-author">doug_gregor</span> </li> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">new</span> </li> <li><strong>severity</strong> → <span class="trac-field-new">Problem</span> </li> </ul> <p> Assigned to "doug_gregor" instead of nonexistent user "dgregor" </p> Ticket Douglas Gregor Thu, 13 Sep 2007 18:23:26 GMT https://svn.boost.org/trac10/ticket/732#comment:2 https://svn.boost.org/trac10/ticket/732#comment:2 <ul> <li><strong>owner</strong> changed from <span class="trac-author">doug_gregor</span> to <span class="trac-author">Douglas Gregor</span> </li> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> <li><strong>description</strong> modified (<a href="/trac10/ticket/732?action=diff&amp;version=2">diff</a>) </li> </ul> Ticket Jeremiah Willcock Tue, 27 Jan 2009 20:07:22 GMT https://svn.boost.org/trac10/ticket/732#comment:3 https://svn.boost.org/trac10/ticket/732#comment:3 <ul> <li><strong>owner</strong> changed from <span class="trac-author">Douglas Gregor</span> to <span class="trac-author">Jeremiah Willcock</span> </li> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">new</span> </li> </ul> Ticket Jeremiah Willcock Tue, 27 Jan 2009 20:07:40 GMT https://svn.boost.org/trac10/ticket/732#comment:4 https://svn.boost.org/trac10/ticket/732#comment:4 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> </ul> Ticket Jeremiah Willcock Tue, 27 Jan 2009 20:19:30 GMT https://svn.boost.org/trac10/ticket/732#comment:5 https://svn.boost.org/trac10/ticket/732#comment:5 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> <span class="trac-field-old">None</span> → <span class="trac-field-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/50815" title="Changed Johnson ASSP algorithm to use combine rather than + to do ...">[50815]</a>) Changed Johnson ASSP algorithm to use combine rather than + to do reweighting (did not change -, though); fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/732" title="#732: Bugs: Johnson All-Pairs needs better &#34;no path&#34; information (closed: fixed)">#732</a> </p> Ticket