弗洛伊德算法例题可以解决无向图最短路径么？

来源：蜘蛛抓取(WebSpider) 时间：2017-12-12 15:20 标签： 弗洛伊德算法例题

迪杰斯特拉算法如果不熟悉的话從这里开始看。。如果已经明白了迪杰斯特拉算法而想知道花费问题、城市之间的物资问题、最短路径条数问题的朋友可以往下翻。。

算法思想是从起点开始找到一条起点能到达顶点中的边权最小的那个点，然后从这个点开始更新起点和该点共有的点的最短路径。思想看起来很好懂实际编码实现还是有难度的。

1、初始时把图（不管是有向图还是无向图） 中的各个边的权重设置为无穷大 从起點到各个点的距离设置为无穷大。 每个点是否经过的标记设置为false

2、从p键盘接受各个点之间的路径 

 
 

 3.开始写迪杰斯特拉算法
 
 

 1）: 将从起点各个點的路径的距离设置为最大，并将起点到自身的距离设置为0；
 
 
 

 2）： 因为有n个顶点所以开始n次循环
 
 

 首先我们设置两个变量，u（是d[u]最小）和minnum（存放最小的d[u])
 
 

 然后找到图中未访问的结点中d[j]的最小值。
 
 

 分支情况：如果找不到则说明剩下的点和s不连通，返回；
 
 

 如果找到：标记u点为訪问过； 开始再次访问图中的结点(记为V )
 
 

 如果该结点未被访问并且u能到该点并且以u为中介点可以让d[v]更小则更新
 
 
 

 
 

  
 

 既然懂了迪杰斯特拉算法，那么题目肯定不会考的这么“裸”最常见的三种问题就是：
 
 

 1：给每条再增加一个边权（比如说花费），然后求在最短的路径有多条时要求路径上的花费最小（也可以是别的含义求最大）
 
 

 2：给每个点增加一个点权（比如从每个城市能收集到的物资），然后在最短路径有多條的时候要求路径上的点权之和最大（同理也可以是最小）
 
 

 3：直接问有多少最短路径
 
 

 
 

 针对一增加边权，那我们在增加一个数组cost[u][v] 表示从u箌v的花费，在增加一个数组c[],作用跟d[]一样初始化时也设置为INF，起点s设置为0在优化边的代码中更改如下：
 
 

  
 

 针对二，增加点权问题我们加┅个数组weight[u]表示城市u中的物资数目，（由题中给出）并增加一个数组w[]，令从起点s到顶点u可以收集到的物资为w[u] .
 
 

  
 

 针对三只需要增加一个数组num[],囹其从起点s到u的最短路径为num[u] ， 初始化时只有num[s] = 1 其余为0
 
 

  
 

 基本上迪杰斯特拉考的问题就这些。注意只是正边权问题！！
 




                            

                                                    

                                

  

    弗洛伊德算法例题求解最短路径,弗洛伊德最短路径算法,弗洛伊德最短路径,最短路径算法,dijkstra最短路径算法,floyd最短路径算法,无向图最短路径算法,图的最短路径算法,java最短路径算法,迷宮最短路径算法
  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 弗洛伊德算法例题 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐