📄 7_10.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 LINK="#0000ff" VLINK="#800080">
<B><FONT FACE="仿宋体" LANG="ZH-CN"><P ALIGN="JUSTIFY">10. </FONT><FONT FACE="宋体" LANG="ZH-CN">用弗洛伊德算法算法求每一对顶点之间的最短路径的算法</P>
</FONT><FONT FACE="仿宋体" LANG="ZH-CN"><P ALIGN="JUSTIFY">void</B> ShortestPath_FLOYD ( MGraph G, PathMatrix <B>&</B>Path, DistancMatrix <B>&</B>Dist ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN">{</P>
</B></FONT><FONT FACE="仿宋体" LANG="ZH-CN"><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN">用弗洛伊德算法求有向图</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">G</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">中各对顶点</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">和</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">w</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">间最短路径</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">Path</I>[<I>v</I>][<I>w</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN">及带权长度</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">Dist</I>[<I>v</I>][<I>w</I>]</FONT><FONT FACE="宋体" LANG="ZH-CN">。</P>
</FONT><FONT FACE="仿宋体" LANG="ZH-CN"><P ALIGN="JUSTIFY">// <I>Path</I>[<I>v</I>][<I>w</I>][<I>u</I>] </FONT><FONT FACE="宋体" LANG="ZH-CN">为</FONT> <FONT FACE="仿宋体" LANG="ZH-CN">TRUE</FONT><FONT FACE="宋体" LANG="ZH-CN">，则</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">u</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">是从</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">到</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">w</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">的当前求得的最短路径上的顶点。</P>
<P ALIGN="JUSTIFY">	</FONT> <B><FONT FACE="仿宋体" LANG="ZH-CN">for</B> ( v = 0; v < G.vexnum; ++v )				// </FONT><FONT FACE="宋体" LANG="ZH-CN">各对顶点之间初始已知路径及距离</P>
<P ALIGN="JUSTIFY">		</FONT><B><FONT FACE="仿宋体" LANG="ZH-CN">for</B> ( w = 0; w , G.vexnum; ++w ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN">{</P>
</B><P ALIGN="JUSTIFY">		</FONT><FONT FACE="仿宋体" LANG="ZH-CN"> Dist[v][w] = G.arcs[v][w];</P>
<P ALIGN="JUSTIFY">		 <B>for</B> ( u = 0; u < G.vexnum; ++u ) Path[v][w][u] = FALSE;</P>
<P ALIGN="JUSTIFY">		 <B>if</B> ( Dist[v][w] < INFINITY ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN">{				</B></FONT><FONT FACE="仿宋体" LANG="ZH-CN">// </FONT><FONT FACE="宋体" LANG="ZH-CN">从</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">到</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">w</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">有直接路径</P>
<P ALIGN="JUSTIFY">			</FONT><FONT FACE="仿宋体" LANG="ZH-CN">Path[v][w][v] = TRUE; Path[v][w][w] = TRUE;</P>
<P ALIGN="JUSTIFY">		 </FONT><B><FONT FACE="宋体" LANG="ZH-CN">}</B></FONT><FONT FACE="仿宋体" LANG="ZH-CN"> // if </FONT><FONT FACE="宋体" LANG="ZH-CN">结束</P>
<P ALIGN="JUSTIFY">		<B>}</B></FONT><FONT FACE="仿宋体" LANG="ZH-CN"> // for </FONT><FONT FACE="宋体" LANG="ZH-CN">结束</P>
<P ALIGN="JUSTIFY">	</FONT> <B><FONT FACE="仿宋体" LANG="ZH-CN">for</B> ( u = 0; u < G.vexnum; ++u )</P>
<P ALIGN="JUSTIFY">		<B>for</B> ( v = 0; v < G.vexnum; ++v )</P>
<P ALIGN="JUSTIFY">		 <B>for</B> ( w = 0; w < G,vexnum; ++w)</P>
<P ALIGN="JUSTIFY">			<B>if</B> ( Dist[v][u] + Dist[u][w] < Dist[v][w] ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN">{</FONT><FONT FACE="仿宋体" LANG="ZH-CN"> </B>// </FONT><FONT FACE="宋体" LANG="ZH-CN">从</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">经</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">u</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">到</FONT> <I><FONT FACE="仿宋体" LANG="ZH-CN">w</I> </FONT><FONT FACE="宋体" LANG="ZH-CN">的一条路径更短</P>
<P ALIGN="JUSTIFY">			</FONT> <FONT FACE="仿宋体" LANG="ZH-CN">Dist[v][w] = Dist[v][u] + Dist[u][w];</P>
<P ALIGN="JUSTIFY">			 <B>for</B> ( i = 0; i < G.vexnum; ++i )</P>
<P ALIGN="JUSTIFY">				Path[v][w][i] = Path[v][u][i] <B>||</B> Path[u][w][i];;</P>
<P ALIGN="JUSTIFY">			</FONT><B><FONT FACE="宋体" LANG="ZH-CN">}</B></FONT><FONT FACE="仿宋体" LANG="ZH-CN"> // if </FONT><FONT FACE="宋体" LANG="ZH-CN">结束</P>
<P ALIGN="JUSTIFY">	<B>}</B></FONT><FONT FACE="仿宋体" LANG="ZH-CN"> // ShortestPath_FLOYD</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -