📄 dijkstra-dijkstravisit.html
字号:
<html><head><title>Code Fragment</title></head><body text=#000000><center></center><br><br><dl><dd><pre> <font color=#ff0080>/** The actual execution of Dijkstra's algorithm. * @param v source vertex. */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>void</font> <font color=#0000ff>dijkstraVisit </font>(Vertex<V> v) { <font color=#ff0080>// store all the vertices in priority queue Q</font> <font color=#ff8000>for</font><font color=#0000ff> </font>(Vertex<V> u: graph.<font color=#0000ff>vertices</font>()) { <font color=#8000a0><font color=#8000a0>int</font> </font>u_dist; <font color=#ff8000>if</font><font color=#0000ff> </font>(u==v) u_dist = 0; <font color=#ff8000>else</font> u_dist = INFINITE; Entry<Integer, Vertex<V>> u_entry = Q.<font color=#0000ff>insert</font>(u_dist, u); <font color=#ff0080>// autoboxing</font> u.<font color=#0000ff>put</font>(ENTRY, u_entry); } <font color=#ff0080>// grow the cloud, one vertex at a time</font> <font color=#ff8000>while</font><font color=#0000ff> </font>(!Q.<font color=#0000ff>isEmpty</font>()) { <font color=#ff0080>// remove from Q and insert into cloud a vertex with minimum distance</font> Entry<Integer, Vertex<V>> u_entry = Q.<font color=#0000ff>min</font>(); Vertex<V> u = u_entry.<font color=#0000ff>getValue</font>(); <font color=#8000a0><font color=#8000a0>int</font> </font>u_dist = u_entry.<font color=#0000ff>getKey</font>(); Q.<font color=#0000ff>remove</font>(u_entry); <font color=#ff0080>// remove u from the priority queue</font> u.<font color=#0000ff>put</font>(DIST,u_dist); <font color=#ff0080>// the distance of u is final</font> u.<font color=#0000ff>remove</font>(ENTRY); <font color=#ff0080>// remove the entry decoration of u</font> <font color=#ff8000>if</font><font color=#0000ff> </font>(u_dist == INFINITE) <font color=#ff8000>continue</font>; <font color=#ff0080>// unreachable vertices are not processed</font> <font color=#ff0080>// examine all the neighbors of u and update their distances</font> <font color=#ff8000>for</font><font color=#0000ff> </font>(Edge<E> e: graph.<font color=#0000ff>incidentEdges</font>(u)) { Vertex<V> z = graph.<font color=#0000ff>opposite</font>(u,e); Entry<Integer, Vertex<V>> z_entry =<font color=#0000ff> </font>(Entry<Integer, Vertex<V>>) z.<font color=#0000ff>get</font>(ENTRY); <font color=#ff8000>if</font><font color=#0000ff> </font>(z_entry != null) { <font color=#ff0080>// check that z is in Q, i.e., not in the cloud</font> <font color=#8000a0><font color=#8000a0>int</font> </font>e_weight =<font color=#0000ff> </font>(Integer) e.<font color=#0000ff>get</font>(WEIGHT); <font color=#8000a0><font color=#8000a0>int</font> </font>z_dist = z_entry.<font color=#0000ff>getKey</font>(); <font color=#ff8000>if</font><font color=#0000ff> </font>( u_dist + e_weight < z_dist ) <font color=#ff0080>// relaxation of edge e = (u,z)</font> Q.<font color=#0000ff>replaceKey</font>(z_entry, u_dist + e_weight); } } } }</dl></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -