`
lindexi-gd
  • 浏览: 140110 次
社区版块
存档分类
最新评论

图论 Warshall 和Floyd 矩阵传递闭包

 
阅读更多

首先我们先说下图论，一般图存储可以使用邻接矩阵，或邻接表，一般使用邻接矩阵在稠密图比较省空间。

我们来说下有向图，一般的有向图也是图，图可以分为稠密图，稀疏图，那么从意思上，稠密图就是点的边比较多，稀疏图就是边比较少的图。为什么稠密图放在矩阵比较省空间，因为邻接表在边之间存储需要多余的指针，而矩阵不需要。

下面这张图：http://blog.csdn.net/tham_/article/details/46048063

这里写图片描述

这里写图片描述

我们只说有向图，我们把有向图存在矩阵

我们先说Warshall，假如我们有一张图

这里写图片描述

我们把这张图存储在矩阵

首先是a，a可以直接到b，那么ab就是1
接着就是b，b可以直接到c，那么bc就是1

Warshall a b c d e
a 0 1 0 0 0
b 0 0 1 0 0
c 0 0 0 1 0
d 1 0 0 0 1
e 0 0 0 0 0

那么Warshall怎么做，他需要做个十字形，因为有个定理，

<nobr><span class="math" id="MathJax-Span-1" style="width: 8.376em; display: inline-block;"><span style="display: inline-block; position: relative; width: 6.669em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.923em 1000em 3.256em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-2"><span class="msubsup" id="MathJax-Span-3"><span style="display: inline-block; position: relative; width: 1.336em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-4" style="font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.749em;"><span class="texatom" id="MathJax-Span-5"><span class="mrow" id="MathJax-Span-6"><span class="mi" id="MathJax-Span-7" style="font-size: 70.7%; font-family: MathJax_Math-italic;">i</span><span class="mi" id="MathJax-Span-8" style="font-size: 70.7%; font-family: MathJax_Math-italic;">j</span></span></span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span><span class="mo" id="MathJax-Span-9" style="font-family: MathJax_Main; padding-left: 0.269em;">=</span><span class="msubsup" id="MathJax-Span-10" style="padding-left: 0.269em;"><span style="display: inline-block; position: relative; width: 1.443em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-11" style="font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.749em;"><span class="texatom" id="MathJax-Span-12"><span class="mrow" id="MathJax-Span-13"><span class="mi" id="MathJax-Span-14" style="font-size: 70.7%; font-family: MathJax_Math-italic;">i</span><span class="mi" id="MathJax-Span-15" style="font-size: 70.7%; font-family: MathJax_Math-italic;">k</span></span></span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span><span class="mo" id="MathJax-Span-16" style="font-family: MathJax_Main; padding-left: 0.216em;">∪</span><span class="msubsup" id="MathJax-Span-17" style="padding-left: 0.216em;"><span style="display: inline-block; position: relative; width: 1.496em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-18" style="font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.749em;"><span class="texatom" id="MathJax-Span-19"><span class="mrow" id="MathJax-Span-20"><span class="mi" id="MathJax-Span-21" style="font-size: 70.7%; font-family: MathJax_Math-italic;">k</span><span class="mi" id="MathJax-Span-22" style="font-size: 70.7%; font-family: MathJax_Math-italic;">j</span></span></span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.337em; vertical-align: -0.463em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-1"> R_{ij} = R_{ik} \cup R_{kj} </script>

其中ijk都是从0到n，这里n是点个数

那么我们得到的第一个矩阵，叫做

<nobr><span class="math" id="MathJax-Span-23" style="width: 1.496em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.176em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.283em 1000em 2.509em -0.424em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-24"><span class="msubsup" id="MathJax-Span-25"><span style="display: inline-block; position: relative; width: 1.176em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-26" style="font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.877em; left: 0.749em;"><span class="mn" id="MathJax-Span-27" style="font-size: 70.7%; font-family: MathJax_Main;">0</span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.27em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-2"> R^0 </script>
那么由第一个矩阵变化出第二个矩阵就叫
<nobr><span class="math" id="MathJax-Span-28" style="width: 1.496em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.176em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.283em 1000em 2.509em -0.424em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-29"><span class="msubsup" id="MathJax-Span-30"><span style="display: inline-block; position: relative; width: 1.176em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-31" style="font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.877em; left: 0.749em;"><span class="mn" id="MathJax-Span-32" style="font-size: 70.7%; font-family: MathJax_Main;">1</span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.27em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-3"> R^1 </script>
然后一直到n，这里n是点个数

如何变化，其实很简单，做个十字，这里说的十字是

这里写图片描述

那么我们第一个公式就可以来

我们选择一个点

这里写图片描述

如果在十字两个都是1，那么这个点也就改为1，因为图里只有一个点可以修改，所以修改完就是

<nobr><span class="math" id="MathJax-Span-33" style="width: 1.496em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.176em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.283em 1000em 2.509em -0.424em); top: -2.344em; left: 0.003em;"><span class="mrow" id="MathJax-Span-34"><span class="msubsup" id="MathJax-Span-35"><span style="display: inline-block; position: relative; width: 1.176em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-36" style="font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.877em; left: 0.749em;"><span class="mn" id="MathJax-Span-37" style="font-size: 70.7%; font-family: MathJax_Main;">1</span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.349em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.27em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-4">R^1</script>

接着我们把十字修改

这里写图片描述

那么发现有两个点，加粗db是上次修改的

我们可以发现ac和dc都是可以修改

这里写图片描述

那么继续修改

这里写图片描述

这里写图片描述

这里写图片描述

这里写图片描述

这里写图片描述

修改后

Warshall a b c d e
a 1 1 1 1 1
b 1 1 1 1 1
c 1 1 1 1 1
d 1 1 1 1 1
e 0 0 0 0 0

因为我们从a到d都是可以到达，所以都为1，因为存在d可以到e，所以所有点都可以到e，因为e本身没有到任何点，所以为0

那么Floyd是什么，其实就是把原先的矩阵1改为数字

Floyd是可以算图中任意两个点的最短路径

那么说道这，我们需要带权有向图

带权就是两个点之间的边有个权，放在矩阵就是可以相连的两个点之间的ij为权

1

Warshall a b c d e
a 0 5
<nobr><span class="math" id="MathJax-Span-38" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-39"><span class="mi" id="MathJax-Span-40" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-5">\infty</script>
<nobr><span class="math" id="MathJax-Span-41" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-42"><span class="mi" id="MathJax-Span-43" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-6">\infty</script>
<nobr><span class="math" id="MathJax-Span-44" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-45"><span class="mi" id="MathJax-Span-46" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-7">\infty</script>
b
<nobr><span class="math" id="MathJax-Span-47" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-48"><span class="mi" id="MathJax-Span-49" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-8">\infty</script>		 0 2
<nobr><span class="math" id="MathJax-Span-50" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-51"><span class="mi" id="MathJax-Span-52" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-9">\infty</script>
<nobr><span class="math" id="MathJax-Span-53" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-54"><span class="mi" id="MathJax-Span-55" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-10">\infty</script>
c
<nobr><span class="math" id="MathJax-Span-56" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-57"><span class="mi" id="MathJax-Span-58" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-11">\infty</script>
<nobr><span class="math" id="MathJax-Span-59" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-60"><span class="mi" id="MathJax-Span-61" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-12">\infty</script>		 0 1
<nobr><span class="math" id="MathJax-Span-62" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-63"><span class="mi" id="MathJax-Span-64" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-13">\infty</script>
d 6 15
<nobr><span class="math" id="MathJax-Span-65" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-66"><span class="mi" id="MathJax-Span-67" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-14">\infty</script>		 0 1
e
<nobr><span class="math" id="MathJax-Span-68" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-69"><span class="mi" id="MathJax-Span-70" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-15">\infty</script>
<nobr><span class="math" id="MathJax-Span-71" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-72"><span class="mi" id="MathJax-Span-73" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-16">\infty</script>
<nobr><span class="math" id="MathJax-Span-74" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-75"><span class="mi" id="MathJax-Span-76" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-17">\infty</script>
<nobr><span class="math" id="MathJax-Span-77" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-78"><span class="mi" id="MathJax-Span-79" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-18">\infty</script>		 0

我们和之前Warshall一样做十字，然后判断是得到

<nobr><span class="math" id="MathJax-Span-1526" style="width: 14.243em; display: inline-block;"><span style="display: inline-block; position: relative; width: 11.363em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.869em 1000em 3.256em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-1527"><span class="msubsup" id="MathJax-Span-1528"><span style="display: inline-block; position: relative; width: 1.336em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-1529" style="font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.749em;"><span class="texatom" id="MathJax-Span-1530"><span class="mrow" id="MathJax-Span-1531"><span class="mi" id="MathJax-Span-1532" style="font-size: 70.7%; font-family: MathJax_Math-italic;">i</span><span class="mi" id="MathJax-Span-1533" style="font-size: 70.7%; font-family: MathJax_Math-italic;">j</span></span></span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span><span class="mo" id="MathJax-Span-1534" style="font-family: MathJax_Main; padding-left: 0.269em;">=</span><span class="mi" id="MathJax-Span-1535" style="font-family: MathJax_Math-italic; padding-left: 0.269em;">m</span><span class="mi" id="MathJax-Span-1536" style="font-family: MathJax_Math-italic;">i</span><span class="mi" id="MathJax-Span-1537" style="font-family: MathJax_Math-italic;">n</span><span class="mo" id="MathJax-Span-1538" style="font-family: MathJax_Main;">{</span><span class="msubsup" id="MathJax-Span-1539"><span style="display: inline-block; position: relative; width: 1.336em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-1540" style="font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.749em;"><span class="texatom" id="MathJax-Span-1541"><span class="mrow" id="MathJax-Span-1542"><span class="mi" id="MathJax-Span-1543" style="font-size: 70.7%; font-family: MathJax_Math-italic;">i</span><span class="mi" id="MathJax-Span-1544" style="font-size: 70.7%; font-family: MathJax_Math-italic;">j</span></span></span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span><span class="mo" id="MathJax-Span-1545" style="font-family: MathJax_Main;">,</span><span class="msubsup" id="MathJax-Span-1546" style="padding-left: 0.163em;"><span style="display: inline-block; position: relative; width: 1.443em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-1547" style="font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.749em;"><span class="texatom" id="MathJax-Span-1548"><span class="mrow" id="MathJax-Span-1549"><span class="mi" id="MathJax-Span-1550" style="font-size: 70.7%; font-family: MathJax_Math-italic;">i</span><span class="mi" id="MathJax-Span-1551" style="font-size: 70.7%; font-family: MathJax_Math-italic;">k</span></span></span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span><span class="mo" id="MathJax-Span-1552" style="font-family: MathJax_Main; padding-left: 0.216em;">+</span><span class="msubsup" id="MathJax-Span-1553" style="padding-left: 0.216em;"><span style="display: inline-block; position: relative; width: 1.496em; height: 0px;"><span style="position: absolute; clip: rect(1.709em 1000em 2.723em -0.424em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-1554" style="font-family: MathJax_Math-italic;">R</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.291em; left: 0.749em;"><span class="texatom" id="MathJax-Span-1555"><span class="mrow" id="MathJax-Span-1556"><span class="mi" id="MathJax-Span-1557" style="font-size: 70.7%; font-family: MathJax_Math-italic;">k</span><span class="mi" id="MathJax-Span-1558" style="font-size: 70.7%; font-family: MathJax_Math-italic;">j</span></span></span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span><span class="mo" id="MathJax-Span-1559" style="font-family: MathJax_Main;">}</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.47em; vertical-align: -0.463em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-117">R_{ij}=min\{R_{ij},R_{ik}+R_{kj}\}</script>

那么这样就可以得到任意两点路径

算法复杂

<nobr><span class="math" id="MathJax-Span-1560" style="width: 3.203em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.563em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.709em 1000em 3.203em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-1561"><span class="mi" id="MathJax-Span-1562" style="font-family: MathJax_Math-italic;">O</span><span class="mo" id="MathJax-Span-1563" style="font-family: MathJax_Main;">(</span><span class="msubsup" id="MathJax-Span-1564"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px;"><span style="position: absolute; clip: rect(1.976em 1000em 2.723em -0.477em); top: -2.557em; left: 0.003em;"><span class="mi" id="MathJax-Span-1565" style="font-family: MathJax_Math-italic;">n</span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span><span style="position: absolute; top: -2.877em; left: 0.589em;"><span class="mn" id="MathJax-Span-1566" style="font-size: 70.7%; font-family: MathJax_Main;">3</span><span style="display: inline-block; width: 0px; height: 2.456em;"></span></span></span></span><span class="mo" id="MathJax-Span-1567" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.537em; vertical-align: -0.397em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-118">O(n^3)</script>

在Warshall是判断两个都为1，修改，Floyd判断两个加起来的值比当前的小，修改

和Warshall一样全部修改就是两个点之间最短距离。

为

<nobr><span class="math" id="MathJax-Span-1568" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-1569"><span class="mi" id="MathJax-Span-1570" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-119">\infty</script>修改如果加上一个数还是
<nobr><span class="math" id="MathJax-Span-1571" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-1572"><span class="mi" id="MathJax-Span-1573" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-120">\infty</script>
任意一个数字小于
<nobr><span class="math" id="MathJax-Span-1574" style="width: 1.283em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.016em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(2.189em 1000em 2.936em -0.424em); top: -2.771em; left: 0.003em;"><span class="mrow" id="MathJax-Span-1575"><span class="mi" id="MathJax-Span-1576" style="font-family: MathJax_Main;">∞</span></span><span style="display: inline-block; width: 0px; height: 2.776em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span></nobr>
<script type="math/tex; mode=display" id="MathJax-Element-121">\infty</script>所以只要存在数字就可以修改
<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>
分享到：
| WPF DataGridHyperlinkColumn
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    c++求传递闭包

    ### C++ 求解传递闭包算法解析 ...利用 Floyd-Warshall 算法不仅能够高效地解决传递闭包问题，而且其简洁的代码结构也便于理解和维护。对于需要处理大量图论问题的应用场景，这种算法是非常实用的工具之一。

    关系概念、传递闭包概念及warshall算法c++程序

    通过阅读和运行这个程序，初学者可以更直观地理解传递闭包的概念，并掌握Warshall算法的实现方式。实践是理论学习的有力补充，结合实例的编程练习能够帮助我们更好地理解和运用这些抽象的数学概念。

    传递闭包的Matlab实现.rar

    在Matlab中实现传递闭包，通常会涉及到矩阵运算和图论算法。 传递闭包的计算可以采用多种方法，包括但不限于Warshall-Floyd算法、Kleene迭代等。Warshall-Floyd算法是一种经典的方法，用于找出所有节点对之间的最短...

    图论- 图的连通性- 传递闭包.rar

    Warshall-Floyd算法则是通过迭代所有可能的三元组(u, v, w)，检查是否能通过w从u到达v，更新传递闭包矩阵，同样具有O(n^3)的时间复杂度。尽管效率较低，但这两个算法在理解和实现上相对直观。 传递闭包在实际应用中...

    warshall算法(c++)

    在计算机科学和图论领域中，Warshall算法是一项非常重要的算法，主要用于解决图论中的传递闭包问题。所谓传递闭包，指的是在一个有向图中，对于任意一对顶点(i, j)，如果在原图中存在一条从顶点i到顶点j的路径，则在...

    2018211958 孙淼 实验四1

    实验四1的主题是关系的闭包运算以及Floyd-Warshall算法的应用，主要涉及了关系理论和图论中的重要概念。在这个实验中，学生需要掌握如何通过编程来计算关系的自反、对称和传递闭包。 关系的闭包运算在离散数学中是...

    我用C++编的离散中的Warshall

    在离散数学中，Warshall算法是一种经典的图论算法，主要用于求解图的传递闭包问题。这个算法是由美国计算机科学家Robert W. Floyd在1962年提出的，因此在一些文献中也被称作Floyd-Warshall算法。在C++编程中实现...

    离散数学warshall算法mfc

    离散数学中的Warshall算法是图论中的一个重要概念，它主要应用于求解图的传递闭包问题。在计算机科学中，尤其是编译器设计、网络路由和数据结构等领域，Warshall算法有着广泛的应用。MFC（Microsoft Foundation ...

    离散数学实验报告——图的可达矩阵实现

    离散数学是计算机科学的基础，其中图论是重要的组成部分。...同时，这也为后续的图算法学习打下了坚实的基础，如最短路径算法（Dijkstra、Floyd-Warshall等）和拓扑排序等，这些都依赖于图的矩阵表示和矩阵运算。

    warshall算法

    另外，对于完全图（每个节点都与其他所有节点相连）和稀疏图（边的数量远小于节点数量的平方），其他更高效的算法如Floyd-Warshall算法可能会更为合适。 总的来说，Warshall算法是图论和系统工程中的一个重要工具，...

    并行计算-实验指导-实验03-图论.doc

    实验03的主题是图论在并行计算中的应用，涵盖了几个关键概念，包括传递闭包、连通分量、单源最短路径和最小生成树。以下是对这些知识点的详细说明： 1. **传递闭包**： - **传递闭包串行算法**：在图论中，传递...

    所有结点对的最短路径问题、ShortestPathsDemo.rar

    本项目通过C#编程语言实现了几种经典算法来解决这一问题，包括Floyd-Warshall算法、有向图的传递闭包以及Johnson算法，特别是针对稀疏图的情况。 首先，Floyd-Warshall算法是一种解决所有结点对最短路径问题的动态...

    集合论与图论课程教学大纲.docx

    - 关系的闭包：掌握等价关系和传递闭包，理解如何求解有限集合上的二元关系闭包。 - 偏序关系与全序：学习偏序集、全序和良序的概念，理解它们在问题解决中的应用。 课程的教学目标旨在提升学生的以下能力： - *...

    图论的两个实用算法的编程1

    为此，作者采用了基于可达性传递闭包的算法，这是一种Floyd-Warshall算法的变种。该算法通过迭代地更新邻接矩阵来标记所有顶点之间是否能够通过一系列边相互到达，从而有效地判断两点间是否存在路径。通过这种方法，...

    北邮通信网实验报告 floyd算法

    Floyd）在1962年提出，并由斯蒂芬·沃思（Stephen Warshall）推广，虽然沃思的版本通常用于布尔矩阵的传递闭包，但Floyd的版本适用于寻找最短路径。 描述提到该报告是北邮通信网四次试验之一，并且包含了可以在...

    YYGVXF4.zip_ajax_gle

    可达矩阵可以通过对邻接矩阵进行幂运算来计算，例如使用Floyd-Warshall算法或者矩阵快速幂等方法。 3. **JAVA语言编程**： JAVA是一种广泛使用的面向对象的编程语言，具有跨平台性、健壮性和安全性等特点。在处理...

    ForeBack.zip_matlab例程_Windows_Unix_

    **Floyd-Warshall算法**是一种用于查找图中所有顶点对之间的最短路径的动态规划算法，也可以用来求解传递闭包。该算法的基本思想是通过不断尝试所有可能的中间节点，更新每一对顶点间的最短距离（或传递关系）。 **...

    Matlab最短路径算法.docx

    它特别适用于处理有向图，并能处理负权重边的情况，同时也可以用于计算有向图的传递闭包。该算法的基本思想是逐步考虑所有中间节点，通过比较经过中间节点的路径和直接连接的路径，不断更新最短路径信息。 算法步骤...

    离散数学小结PPT课件.pptx

    - 最短路径算法，如Dijkstra算法和Floyd-Warshall算法。 9. **树 (Trees)**： - 树的定义、性质（如高度、分支、叶节点）和树的遍历方法。 - 搜索树，如二叉搜索树和AVL树。 10. **布尔代数 (Boolean Algebra)*...

Magicbox
Global site tag (gtag.js) - Google Analytics