摘要：floyd算法的三重循环问题 佛洛依德短距离，算法就是这么计算的，如果不是在外层，这就没逻辑了，求不出短距离了
floyd算法的三重循环问题
佛洛依德短距离，算法就是这么计算的，如果不是在外层，这就没逻辑了，求不出短距离了。你需要仔细思考一下。
佛洛依德：floyd算法的三重循环问题
佛洛依德：floyd算法的三重循环问题
佛洛依德：floyd算法的三重循环问题
floyd的根本思想是动态规划，外层枚举的k是表示新加入一个可以作为中间点的顶点
floyd的核心思路是
求弗洛伊德算法的详细解释~
floyd算法思想：1，构建一个邻接矩阵存储任意两点之间的权值如图D0.
2、例如求v1,v4之间的短路径。先增加v2做中间顶点，D[1][4]=∞。if（D[1][4]>D[1][2]+D[2]4]）=6+4）D[1][4]=10;这样就可以了。
3、如不能在离得较远的两点(例v1,v9）直接得到上述可以满足if的中间点，则跟据你书本的代码可以先构建原点到中间点的短路径，继而就可以求得vi,v9之间的短路径
Floyed算法变形的过程里，dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]) 这个语句的意思
算法描述：
(1) 用数组dis[i][j]来记录i,j之间的短距离。初始化dis[i][j],若i=j则dis[i][j]=0,
若i,j之间有边连接则dis[i][j]的值为该边的权值，否则dis[i][j]的值为 。
(2) 对所有的k值从1到n，修正任意两点之间的短距离，计算dis[i][k]+dis[k][j]的值，
若小于dis[i][j],则dis[i][j]= dis[i][k]+dis[k][j]，否则dis[i][j]的值不变。
程序：
void Floyd(int dis[n+1][n+1],int path[n+1][n+1],int n)
{int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(dis[i][k]+dis[k][j] {dis[i][j] = dis[i][k]+dis[k][j]; Path[i][j]=k; }} 正确性证明(归纳法) ： 对于任意两点A，B： （1） 当从A到B之间的短路径，在中间没有经过顶点或经过1个顶点号为1的顶点时，算法显然正确。 （2） 设A到B经过的顶点号不超过k-1时，算法得到的短距离是正确的 （3） 当A到B经过的顶点号为k时，则从A到顶点号为k的顶点v 之间的顶点号均不大于k-1，从v 到B之间的顶点号也不大于k-1，由设2得，A到vk的距离是中间顶点号不超过k-1的短距离，vk到B的距离是中间顶点号不超过k-1的短距离，所以A经vk到B为A，B之间经过号为k的路径中距离短的，由算法修正A，B的短距离，即可得到A，B间顶点号不超过k的短距离。 （4） 综上所述，算法是正确的 时间复杂度：O（n3） 实际上这里包含两个问题： 问题一：如何判断给定的链表是以NULL结尾，还是形成了一个环？ 思路分析： 蛮力法：从表头开始遍历，针对每个均检查是否存在它之后的某个的后继指针指向该，如果存在则说明该链表存在环。如果一直遍历到表尾都未发现这种，则说明该链表不存在环。很显然这种算法是一种效率的算法，因此不考虑使用 使用散列表（哈希表）：从表头开始逐个遍历链表中的每个，并检查其是否已经存在散列表中。如果存在则说明已经访问过该了，也就是存在环；如果一直到表尾都没有出现已经访问过的，则说明该链表不存在环。时间复杂度：O(n) Floyd环判定算法：使用两个在链表中具有不同移动速度的指针（如：fastNode每次移动两个，slowNode每次移动一个），两个指针同时从表头开始移动，如果在某一时刻它们相遇了，则表明该链表存在环。原因很简单：快速移动指针和慢速移动指针将会指向同一位置的可能情况就是整个或者部分链表是一个环 问题二：如果链表中存在环，找到环的入口 思路分析： 首先使用Floyd环判定算法判断一个链表是否存在环。在找到环之后，将slowNode重新设置为表头，接下来slowNode和fastNode每次分别移动一个，当它们再次相遇时即为环的起始 时间复杂度：O(n) 证明： 设飞环长度为：C1，整个环的长度为：C2，两个指针相遇时走过的环中的弧长为：C3 次相遇时： Sslow = C1 + C3 Sfast = C1 + C2 + C3 且：Sfast = 2Sslow 则：C1 = C2 – C3 当slowNode重置为表头，两个指针只需要分别移动C1即可第二次相遇： slowNode移动长度：C1，此时slowNode的位置是环的开始 fastNode移动长度：C1 = C2 – C3，也就是说fastNode此时的位置是：初始位置C3 + C2 – C3 = C2，也就是说fastNode此时刚好移动到环的开始，二者相遇 示例代码： 定义一个单向链表的单个： package cn.zifangsky.linkedlist; / 单链表的定义 @author zifangsky / public class SinglyNode { private int data; // 数据 private SinglyNode next; // 该的下个 public SinglyNode(int data) { this.data = data; }public SinglyNode(int data, SinglyNode next) { this.data = data; this.next = next; }public int getData() { return data; }public void setData(int data) { this.data = data; }public SinglyNode getNext() { return next; }public void setNext(SinglyNode next) { this.next = next; }@Override public String toString() { return "SinglyNode [data=" + data + "]"; }} package cn.zifangsky.linkedlist.questions; import org.junit.Test; import cn.zifangsky.linkedlist.SinglyNode; / 判断给定的链表是以NULL结尾，还是形成了一个环？如果链表中存在环，则找到环的起始 @author zifangsky / public class Question3 { / 在找到环之后，将slowNode重新设置为表头，接下来slowNode和fastNode每次分别移动一个， 当它们再次相遇时即为环的起始 @时间复杂度 O(n) @param headNode @return / public SinglyNode findLoopStartNode(SinglyNode headNode){ SinglyNode fastNode=headNode,slowNode=headNode; boolean loopExists = false; //是否存在环的标识 while(slowNode.getNext() != null && fastNode.getNext() != null && fastNode.getNext().getNext() != null){ slowNode = slowNode.getNext(); fastNode = fastNode.getNext().getNext(); if(slowNode == fastNode){ loopExists = true; break; }} //如果存在环，则slowNode回到表头 if(loopExists){ slowNode = headNode; while(slowNode != fastNode){ slowNode = slowNode.getNext(); fastNode = fastNode.getNext(); }return fastNode; }return null; }@Test public void testMods(){ SinglyNode headNode1 = new SinglyNode(11); SinglyNode currentNode = headNode1; for(int i=2;i<=5;i++){ SinglyNode tmpNode = new SinglyNode(11 i); currentNode.setNext(tmpNode); currentNode = tmpNode; }//链表headNode2，人为构造了一个环 SinglyNode headNode2 = new SinglyNode(11); SinglyNode ringStartNode = null; currentNode = headNode2; for(int i=2;i<=8;i++){ SinglyNode tmpNode = new SinglyNode(11 i); currentNode.setNext(tmpNode); currentNode = tmpNode; if(i == 3){ ringStartNode = tmpNode; }else if(i == 8){ tmpNode.setNext(ringStartNode); }} System.out.println("链表headNode1的环的起始：" + findLoopStartNode(headNode1) + "；链表headNode2的环的起始：" + findLoopStartNode(headNode2)); }}后测试用例的输出如下： 链表headNode1的环的起始：null；链表headNode2的环的起始：SinglyNode [data=33]注：上面代码中只给出了经典的Floyd环判定算法的实现方式，其他实现方式可以自行网上搜索或者参考我博客上的示例 （PS：纯手打，望采纳！） 有 N 个网络，标记为 1 到 N 。 给定一个列表 times ，表示信号经过 有向 边的传递时间。 times[i] = (u, v, w) ，其中 u 是源， v 是目标， w 是一个信号从源传递到目标的时间。 现在，我们从某个 K 发出一个信号。需要多久才能使所有都收到信号？如果不能使所有收到信号，返回 -1 。 示例： 注意: 本题为一个图算法题，两点之间的时间可以抽象成路程，那么本题相当于求某一点到其他各点的短路径，然后求出各点短路径的值。 常见的短路问题分为两类： 单源短路 和 多源短路 。前者只需要求一个 固定的起点 到各个顶点的短路径，后者则要求得出 任意两个顶点 之间的短路径。 Dijkstra(迪杰斯特拉)算法是典型的 单源短路径算法 ，用于计算一个到其他所有的短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。算法主要的思想是 贪心法 。 适用范围 使用步骤 Floyd算法是一个经典的 动态规划 算法。是解决 任意两点间的短路径 (称为多源短路径问题)的一种算法，可以正确处理有向图或负权的短路径问题。 其核心思想就是从任意u到任意v的短路径有2种： 所以，我们设graph(u,v)为u到v的短路径的距离(当然，不同的题目代表的不一样，比如有的可能是花费，需要灵活变通)，对于每一个k(1~N个)，我们检查graph(u,k) + graph(k,v) < graph(u,v)是否成立，如果成立，证明从u到k再到v的路径比u直接到v的路径短，我们便设置graph(u,v) = graph(u,k) + graph(k,v)，当我们遍历完所有k，graph(u,v)中记录的便是u到v的短路径的距离。 适用范围 使用步骤 2.1、根据k为中间跳更新(u, v)的短距离 Dijkstra算法 Floyd算法 (十分) 堆优化版的Dijkstra算法 参考链接：判断链表是否有环 找到环的入口
Leetcode每日一题(3)
