📄 7_9.htm
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb_2312-80">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<TITLE>第 2 章 线性表</TITLE>
</HEAD>
<BODY>
<B><FONT SIZE=3><P ALIGN="JUSTIFY">9. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>用迪杰斯特拉算法求某个源点到其他顶点的最短路径的算法</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">void</B> ShortestPath_DIJ ( MGraph G, <B>int</B> v0, PathMatrix <B>&</B>Path, ShortPathTable <B>&</B>Dist ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>用迪杰斯特拉算法求有向图</FONT><FONT SIZE=3> <I>G</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>顶点</FONT><FONT SIZE=3> <I>v</I>0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>到其余顶点</FONT><FONT SIZE=3> <I>v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>最短路径</FONT><FONT SIZE=3> <I>Path</I>[<I>v</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>及其带权长度</FONT><FONT SIZE=3> <I>Dist</I>[<I>v</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>当</FONT><FONT SIZE=3> <I>Path</I>[<I>v</I>][<I>w</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>为</FONT><FONT SIZE=3> TRUE</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，则</FONT><FONT SIZE=3> <I>w</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>是从</FONT><FONT SIZE=3> <I>v</I>0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>到</FONT><FONT SIZE=3> <I>v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的当前求得的最短路径上的顶点。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>当</FONT><FONT SIZE=3> <I>final</I>[<I>v</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>为</FONT><FONT SIZE=3> TRUE</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，且仅当</FONT><FONT SIZE=3> <I>v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>∈</FONT><I><FONT SIZE=3>S</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，即已经求得从顶点</FONT><FONT SIZE=3> <I>v</I>0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>到</FONT><FONT SIZE=3> <I>v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的最短路径。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> <B>for</B> ( v = 0; v < G.vexnum; ++v ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>final[v] = FALSE;</P><DIR>
<P ALIGN="JUSTIFY">Dist[v] = G.arcs[v0][v];</P></DIR>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><B><FONT SIZE=3>for</B> ( w = 0; w < G.vexnum; ++w )</P><DIR>
<P ALIGN="JUSTIFY"> Path[v][w] = FALSE;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>设空路径</P></DIR>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><B><FONT SIZE=3>if</B> ( Dist[v] < INFINITY ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P><DIR>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> Path[v][v0] = TRUE;</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>Path[v][v] = TRUE;</P>
</FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">}</FONT><FONT SIZE=3> </B>// if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P></DIR>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // for </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> Dist[v0] = 0; final[v0] = TRUE;</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>				</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>初始化，顶点</FONT><FONT SIZE=3> <I>v</I>0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>属于</FONT><FONT SIZE=3> <I>S</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>集</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>下面开始主循环，每次求得顶点</FONT><FONT SIZE=3> <I>v</I>0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>到某个顶点</FONT><FONT SIZE=3> <I>v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的最短路径，</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>并将顶点</FONT><FONT SIZE=3> <I>v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>加到</FONT><FONT SIZE=3> <I>S</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>集中</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>for</B> ( i = 1; i < G.vexnum; ++i ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</B></FONT><FONT SIZE=3> 		// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>其余</FONT><FONT SIZE=3> G.vexnum-1 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个顶点</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>min = INFNITY;		 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> 	// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>当前所知离</FONT><FONT SIZE=3> <I>v</I>0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的最近距离</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><B><FONT SIZE=3>for</B> ( w = 0; w < G,vexnum; ++w )</P>
<P ALIGN="JUSTIFY">	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>if</B> ( <B>!</B> final[w] )	 	 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3> 		// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>顶点</FONT><FONT SIZE=3> <I>w</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>在</FONT><FONT SIZE=3> <I>V</I>-<I>S</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>中</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><B><FONT SIZE=3>if</B> ( Dist[w] < min ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> v = w; min = Dist[w]	 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> 		// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>顶点</FONT><FONT SIZE=3> <I>w</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>离顶点</FONT><FONT SIZE=3> <I>v</I>0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>更近</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		<B>}</B></FONT><FONT SIZE=3> // if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> final[v] = TRUE;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>				</FONT><FONT SIZE=3> 		// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>离</FONT><FONT SIZE=3> <I>v</I>0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>最近的</FONT><FONT SIZE=3> <I>v </I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>加入</FONT><FONT SIZE=3> <I>S </I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>集</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>for</B> ( w = 0; w < G.vexnum; ++w ) 		// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>更新当前最短路径及距离</P>
<P ALIGN="JUSTIFY">			</FONT><B><FONT SIZE=3>if</B> ( <B>!</B> final[w] <B>&&</B> ( min + G.arcs[v][w] < Dist[w] ) ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">			</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>修改</FONT><FONT SIZE=3> <I>Dist</I>[<I>w</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>和</FONT><FONT SIZE=3> <I>Path</I>[<I>w</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，</FONT><I><FONT SIZE=3>w</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>∈</FONT><I><FONT SIZE=3>V</I>-<I>S</P>
</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3> Dist[w] = min + G.arcs[v][w];</P>
<P ALIGN="JUSTIFY">	 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3> Path[w] = Path[v];</P><DIR>
<DIR>
<P ALIGN="JUSTIFY"> Path[w][w] = TRUE;</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// <I>Path</I>[<I>w</I>] = <I>Path</I>[<I>v</I>] + [<I>w</I>]</P></DIR>
</DIR>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">			<B>}</B></FONT><FONT SIZE=3> // if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // for </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><B><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // ShortestPath_DIJ</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -