📄 dijkstraiterator.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"><!--NewPage--><HTML><HEAD><!-- Generated by javadoc (build 1.4.2_13) on Tue Jun 05 11:36:40 GMT-05:00 2007 --><META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><TITLE>DijkstraIterator (Geotools 2.3.x 2.3.2 API)</TITLE><META NAME="keywords" CONTENT="org.geotools.graph.traverse.standard.DijkstraIterator class"><META NAME="keywords" CONTENT="init()"><META NAME="keywords" CONTENT="next()"><META NAME="keywords" CONTENT="cont()"><META NAME="keywords" CONTENT="killBranch()"><META NAME="keywords" CONTENT="getCost()"><META NAME="keywords" CONTENT="getParent()"><META NAME="keywords" CONTENT="getQueue()"><META NAME="keywords" CONTENT="getRelated()"><LINK REL ="stylesheet" TYPE="text/css" HREF="../../../../../stylesheet.css" TITLE="Style"><SCRIPT type="text/javascript">function windowTitle(){ parent.document.title="DijkstraIterator (Geotools 2.3.x 2.3.2 API)";}</SCRIPT></HEAD><BODY BGCOLOR="white" onload="windowTitle();"><!-- ========= START OF TOP NAVBAR ======= --><A NAME="navbar_top"><!-- --></A><A HREF="#skip-navbar_top" title="Skip navigation links"></A><TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY=""><TR><TD COLSPAN=3 BGCOLOR="#EEEEFF" CLASS="NavBarCell1"><A NAME="navbar_top_firstrow"><!-- --></A><TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY=""> <TR ALIGN="center" VALIGN="top"> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../../overview-summary.html"><FONT CLASS="NavBarFont1"><B>Overview</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-summary.html"><FONT CLASS="NavBarFont1"><B>Package</B></FONT></A> </TD> <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> <FONT CLASS="NavBarFont1Rev"><B>Class</B></FONT> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="class-use/DijkstraIterator.html"><FONT CLASS="NavBarFont1"><B>Use</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A> </TD> </TR></TABLE></TD><TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM></EM></TD></TR><TR><TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2"> <A HREF="../../../../../org/geotools/graph/traverse/standard/DepthFirstTopologicalIterator.html" title="class in org.geotools.graph.traverse.standard"><B>PREV CLASS</B></A> <A HREF="../../../../../org/geotools/graph/traverse/standard/DijkstraIterator.DijkstraNode.html" title="class in org.geotools.graph.traverse.standard"><B>NEXT CLASS</B></A></FONT></TD><TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2"> <A HREF="../../../../../index.html" target="_top"><B>FRAMES</B></A> <A HREF="DijkstraIterator.html" target="_top"><B>NO FRAMES</B></A> <SCRIPT type="text/javascript"> <!-- if(window==top) { document.writeln('<A HREF="../../../../../allclasses-noframe.html"><B>All Classes</B></A>'); } //--></SCRIPT><NOSCRIPT> <A HREF="../../../../../allclasses-noframe.html"><B>All Classes</B></A></NOSCRIPT></FONT></TD></TR><TR><TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2"> SUMMARY: <A HREF="#nested_class_summary">NESTED</A> | FIELD | <A HREF="#constructor_summary">CONSTR</A> | <A HREF="#method_summary">METHOD</A></FONT></TD><TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">DETAIL: FIELD | <A HREF="#constructor_detail">CONSTR</A> | <A HREF="#method_detail">METHOD</A></FONT></TD></TR></TABLE><A NAME="skip-navbar_top"></A><!-- ========= END OF TOP NAVBAR ========= --><HR><!-- ======== START OF CLASS DATA ======== --><H2><FONT SIZE="-1">org.geotools.graph.traverse.standard</FONT><BR>Class DijkstraIterator</H2><PRE><A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html" title="class or interface in java.lang">Object</A> <IMG SRC="../../../../../resources/inherit.gif" ALT="extended by"><A HREF="../../../../../org/geotools/graph/traverse/basic/AbstractGraphIterator.html" title="class in org.geotools.graph.traverse.basic">AbstractGraphIterator</A> <IMG SRC="../../../../../resources/inherit.gif" ALT="extended by"><A HREF="../../../../../org/geotools/graph/traverse/basic/SourceGraphIterator.html" title="class in org.geotools.graph.traverse.basic">SourceGraphIterator</A> <IMG SRC="../../../../../resources/inherit.gif" ALT="extended by"><B>DijkstraIterator</B></PRE><DL><DT><B>All Implemented Interfaces:</B> <DD><A HREF="../../../../../org/geotools/graph/traverse/GraphIterator.html" title="interface in org.geotools.graph.traverse">GraphIterator</A></DD></DL><DL><DT><B>Direct Known Subclasses:</B> <DD><A HREF="../../../../../org/geotools/graph/traverse/standard/DirectedDijkstraIterator.html" title="class in org.geotools.graph.traverse.standard">DirectedDijkstraIterator</A></DD></DL><HR><DL><DT>public class <B>DijkstraIterator</B><DT>extends <A HREF="../../../../../org/geotools/graph/traverse/basic/SourceGraphIterator.html" title="class in org.geotools.graph.traverse.basic">SourceGraphIterator</A></DL><P>Iterates over the nodes of a graph in pattern using <B>Dijkstra's Shortest Path Algorithm</B>. A Dijkstra iteration returns nodes in an order of increasing cost relative to a specified node (the source node of the iteration).<BR> <BR> In a Dijsktra iteration, a <B>weight</B> is associated with each edge and a <B>cost</B> with each node. The iteration operates by maintaining two sets of nodes. The first the set of nodes whose final cost is known, and the second is the set of nodes whose final cost is unknown. Initially, every node except for the source node has a cost of infinity, and resides in the unkown set. The source node has a cost of zero, and is is a member of the known set.<BR> <BR> The iteration operatates as follows:<BR> <PRE> sn = source node of iteration N = set of all nodes K = set of nodes with known cost = {sn} U = set of nodes with unknown cost = N - K cost(sn) = 0 for each node $un in U cost(un) = infinity while(|U| > 0) for each node n in K find a node un in U that relates to n if cost(n) + weight(n,un) < cost(un) cost(un) = cost(n) + weight(n,un) ln = node with least cost in U remove ln from U add ln to K return ln as next node in iteration </PRE> The following is an illustration of the algorithm. Edge weights are labelled in blue and the final node costs are labelled in red.<BR> <IMG src="doc-files/dijkstra.gif"/> <BR> The nodes are returned in order of increasing cost which yields the sequence A,C,B,D,E,F,G,H,I.<BR><P><P><DL><DT><B>Author:</B></DT> <DD>Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net</DD><DT><B>Module:</B></DT><DD><CODE><B>ext/graph</B></CODE> (<A HREF="http://maven.geotools.fr/repository/org/geotools/gt2-graph/"><CODE>gt2-graph.jar</CODE></A>) (<A HREF="http://maven.geotools.fr/reports/graph/index.html">Maven report</A>) (<A HREF="http://svn.geotools.org/geotools/tags/2.3.2/ext/graph/src/org/geotools/graph/traverse/standard/DijkstraIterator.java">SVN head</A>)</DD></DL><HR><P><!-- ======== NESTED CLASS SUMMARY ======== --><A NAME="nested_class_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TD COLSPAN=2><FONT SIZE="+2"><B>Nested Class Summary</B></FONT></TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected static class</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../org/geotools/graph/traverse/standard/DijkstraIterator.DijkstraNode.html" title="class in org.geotools.graph.traverse.standard">DijkstraIterator.DijkstraNode</A></B></CODE><BR> Internal data structure used to track node costs, and parent nodes.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>static interface</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../org/geotools/graph/traverse/standard/DijkstraIterator.EdgeWeighter.html" title="interface in org.geotools.graph.traverse.standard">DijkstraIterator.EdgeWeighter</A></B></CODE><BR> Supplies a weight for each edge in the graph to be used by the iteration when calculating node costs.</TD></TR></TABLE> <!-- =========== FIELD SUMMARY =========== --><!-- ======== CONSTRUCTOR SUMMARY ======== --><A NAME="constructor_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TD COLSPAN=2><FONT SIZE="+2"><B>Constructor Summary</B></FONT></TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD><CODE><B><A HREF="../../../../../org/geotools/graph/traverse/standard/DijkstraIterator.html#DijkstraIterator(org.geotools.graph.traverse.standard.DijkstraIterator.EdgeWeighter)">DijkstraIterator</A></B>(<A HREF="../../../../../org/geotools/graph/traverse/standard/DijkstraIterator.EdgeWeighter.html" title="interface in org.geotools.graph.traverse.standard">DijkstraIterator.EdgeWeighter</A> weighter)</CODE><BR> Constructs a new Dijkstra iterator which uses the specided EdgeWeighter.</TD></TR></TABLE> <!-- ========== METHOD SUMMARY =========== --><A NAME="method_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TD COLSPAN=2><FONT SIZE="+2"><B>Method Summary</B></FONT></TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> void</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../org/geotools/graph/traverse/standard/DijkstraIterator.html#cont(org.geotools.graph.structure.Graphable, org.geotools.graph.traverse.GraphTraversal)">cont</A></B>(<A HREF="../../../../../org/geotools/graph/structure/Graphable.html" title="interface in org.geotools.graph.structure">Graphable</A> current, <A HREF="../../../../../org/geotools/graph/traverse/GraphTraversal.html" title="interface in org.geotools.graph.traverse">GraphTraversal</A> traversal)</CODE><BR> Looks for adjacent nodes to the current node which are in the adjacent node and updates costs.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> double</CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../org/geotools/graph/traverse/standard/DijkstraIterator.html#getCost(org.geotools.graph.structure.Graphable)">getCost</A></B>(<A HREF="../../../../../org/geotools/graph/structure/Graphable.html" title="interface in org.geotools.graph.structure">Graphable</A> component)</CODE><BR> Returns the internal cost of a node which has been calculated by the iterator.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> <A HREF="../../../../../org/geotools/graph/structure/Graphable.html" title="interface in org.geotools.graph.structure">Graphable</A></CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../org/geotools/graph/traverse/standard/DijkstraIterator.html#getParent(org.geotools.graph.structure.Graphable)">getParent</A></B>(<A HREF="../../../../../org/geotools/graph/structure/Graphable.html" title="interface in org.geotools.graph.structure">Graphable</A> component)</CODE><BR> Returns the last node in the known set to update the node. </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected <A HREF="../../../../../org/geotools/graph/util/PriorityQueue.html" title="class in org.geotools.graph.util">PriorityQueue</A></CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../org/geotools/graph/traverse/standard/DijkstraIterator.html#getQueue()">getQueue</A></B>()</CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/util/Iterator.html" title="class or interface in java.util">Iterator</A></CODE></FONT></TD><TD><CODE><B><A HREF="../../../../../org/geotools/graph/traverse/standard/DijkstraIterator.html#getRelated(org.geotools.graph.structure.Graphable)">getRelated</A></B>(<A HREF="../../../../../org/geotools/graph/structure/Graphable.html" title="interface in org.geotools.graph.structure">Graphable</A> current)</CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> void</CODE></FONT></TD>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -