📄 content-7-2.htm
字号:
不可达,称 R 为图 G 的可达性矩阵. </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
权矩阵定义:</b>若G维权图,同样可以定义G的邻接矩阵(权矩阵)R=<img border="0" src="Image/rij_nn.gif" width="38" height="17">,其中 </p>
<div align="center">
<center>
<table border="0" width="40%" cellspacing="0" cellpadding="0" height="47">
<tr>
<td width="21%" rowspan="2" valign="middle" align="center" height="47"><img border="0" src="Image/rij.gif" width="12" height="13">=<font size="6"><b>{</b></font></td>
<td width="79%" height="23">0, 若<img src="IMAGE/vi.gif" width="10" height="11">与<img border="0" src="IMAGE/vj.gif" width="12" height="13">不相邻</td>
</tr>
<tr>
<td width="79%" height="24">权重, 若<img src="IMAGE/vi.gif" width="10" height="11">与<img border="0" src="IMAGE/vj.gif" width="12" height="13">相邻</td>
</tr>
</table>
</center>
</div>
<p style="line-height: 150%">如下图的权矩阵为: </p>
<p style="line-height: 150%" align="center"> <img border="0" src="Image/tu26.gif" width="171" height="146"> </p>
<div align="center">
<table border="0" width="61%">
<tr>
<td width="18%" align="center">
<p align="right">R=</td>
<td width="82%" align="center">
<p align="left"><textarea rows="8" name="S1" cols="38"></textarea></td>
</tr>
</table>
</div>
<p style="line-height: 150%"><font color="#FF0000">但是</font>对于权矩阵而言,R<sup>2</sup>就没有前面定理所说的意义了. </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"><a href="#content-7-2" >返回</a> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%" align="center"><font size="5"><b><a name="最短路径问题">最短路径问题</a></b></font> </p>
<p style="line-height: 150%">
由可达矩阵，我们可以知道某两个结点 <img src="IMAGE/vi.gif" width="10" height="11">
到 <img border="0" src="IMAGE/vj.gif" width="12" height="13">
是否可达，但是具体他们之间的路径如何，哪一条是 <img src="IMAGE/vi.gif" width="10" height="11">
到 <img border="0" src="IMAGE/vj.gif" width="12" height="13">
的最短路径，这就无法看出了，这里我们介绍一种算法：Dijkstron
算法。 </p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu27.gif" width="246" height="123"> </p>
<p style="line-height: 150%" align="center">求A到F的最短距离 </p>
<p style="line-height: 150%"><b> 相关概念</b> </p>
<p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
</b><b>指标<br>
</b> 设 T <img border="0" src="Image/baohan.gif" width="11" height="10"> V,P=V-T
且 a <img border="0" src="Image/bushuyu.gif" width="12" height="12"> T 对<img border="0" src="Image/renyi.gif" width="9" height="11">t,t<img border="0" src="Image/shuyu.gif" width="13" height="11">T，设
l(t)表示从a到t的所有通路中距离最短的一条的长度，且这条路径中不包含T众人和其他的结点，则称l(t)为t关于集合P的指标，若不存在这样的路径，这记l(t)=<img border="0" src="Image/wuqiongda.gif" width="11" height="7"> </p>
<p style="line-height: 150%">注：l(t)不一定是从a到t的最短路径，因为最短路径中可能包含T中其他的节点。 </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
定理1<br>
</b>若t是T中关于P由最小指标的结点，则l(t)是a和t之间的最短距离。 </p>
<p style="line-height: 150%"><b>证明：</b>假设存在一条从a到t的路径其长度小于l(t)<br>
则，这条路径 e 必定包含T-{t}中的至少一个结点，<br>
设，t1是从 a 出发的路径 e
上遇到的T-{t}中的第一个结点，即t1<img border="0" src="Image/shuyu.gif" width="13" height="11">T且t1<img border="0" src="Image/buden.gif" width="8" height="8">t,<br>
则，l(t1) < l(t) ,这与 t
具有最小指标相矛盾。# </p>
<p style="line-height: 150%"> 在对 T 中的任一个 t
计算l(t)时只要同时记录下产生l(t)这条路径的结点序列，也就确定了从
a 到 t 的最短路径。 </p>
<p style="line-height: 150%">例： </p>
<table border="0" width="100%">
<tr>
<td width="37%"><img border="0" src="Image/tu27.gif" width="246" height="123"></td>
<td width="63%">设 T=<input type="text" name="T1" size="10" value="{c,d,e,f}">,P=<input type="text" name="T1" size="8" value="{a,b}"><br>
则，l(c)=<input type="text" name="T1" size="8"><br>
l(d)=<input type="text" name="T1" size="8"> <br>
l(e)=<input type="text" name="T1" size="8"><br>
l(f)=<input type="text" name="T1" size="8"><br>
最小指标为：<input type="text" name="T1" size="8">，<br>
最短路径为：<input type="text" name="T1" size="8"></td>
</tr>
</table>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
定理2<br>
</b>设 T <img border="0" src="Image/baohan.gif" width="11" height="10">
V,P=V-T，设<br>
(1)对P中的任一点p,存在一条从a到p的最短路径,这条路径仅有P中的点构成,<br>
(2)对于每一点t,它关于P的指标为l(t),令x为最小指标所在的点,<br>
即:l(x)=min(l(t)) (t<img border="0" src="Image/shuyu.gif" width="13" height="11">T),<br>
(3)令P'=P<img border="0" src="Image/bing.gif" width="14" height="14">{x},T'=T-{x},l'(t)表示T'中结点t关于P'的指标,则<br>
l'(t)=min{l(t),l(x)+w(x,t)}
其中: </p>
<div align="center">
<table border="0" width="54%" cellspacing="0" cellpadding="0" height="46">
<tr>
<td width="33%" rowspan="2" valign="middle" align="center" height="46">
<p align="right">w(x,t)=</p>
</td>
<center>
<td width="11%" rowspan="2" valign="middle" align="center" height="46"><font size="6"><b>{</b></font></td>
<td width="56%" height="22">x与t之间的边的权重</td>
</tr>
<tr>
<td width="56%" height="24"><img border="0" src="Image/wuqiongda.gif" width="11" height="7">(x与t之间没有边)</td>
</tr>
</table>
</center>
</div>
<p style="line-height: 150%"><b>证明:<br>
</b>为了得到从a到t的且不包含T'中任何结点的一条最短路径可以分成两种情况,<br>
(1) 存在一条既不包含T'中的结点,也不包含x的路径,此时t关于P'的指标是l(t)<br>
(2)
存在一条从a到x且不包含T'中结点,再加上边(x,t)组成的路径.这时t关于P'的指标是:l(x)+w(x,t) </p>
<p style="line-height: 150%"> 所以:l'(t)=min{l(t),l(x)+w(x,t)} </p>
<p style="line-height: 150%">例:P={a,b},T={c,d,e,f} </p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu27.gif" width="246" height="123"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
Djikstra算法(</b>求A到F的最短距离<b>)</b> </p>
<p style="line-height: 150%"> 1、初始化，P={a}，T=V-{a}，对每个结点t计算
l(t)=w(a,t) </p>
<p style="line-height: 150%"> 2、设x为T中关于P有最小指标的点,即:l(x)=min(l(t))
(t<img border="0" src="Image/shuyu.gif" width="13" height="11">T), </p>
<p style="line-height: 150%"> 3、若x=f,则算法结束;<br>
否则,令P'=P<img border="0" src="Image/bing.gif" width="14" height="14">{x},T'=T-{x}<br>
按照公式l'(t)=min{l(t),l(x)+w(x,t)},计算T'中每一个结点t'关于P'的指标. </p>
<p style="line-height: 150%"> 4、P'代替P,T'代替T,重复步骤2,3 </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"><b>例:求A到F的最短距离</b> </p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu27.gif" width="246" height="123"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"><a href="#content-7-2" >返回</a> </p>
<p style="line-height: 150%"> </p>
</td>
</tr>
</table>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p><p align="right"><b><a href="contentFrame-mulu.htm"><<back</a></b>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -