网站制作公司新鸿儒,大庆 网站制作,百度app最新版本,网络营销的案例有哪些戳蓝字“CSDN云计算”关注我们哦#xff01;技术头条#xff1a;干货、简洁、多维全面。更多云计算精华知识尽在眼前#xff0c;get要点、solve难题#xff0c;统统不在话下#xff01;————— 第二天 —————小灰的思路如下#xff1a;第一步#xff0c;利用迪… 戳蓝字“CSDN云计算”关注我们哦技术头条干货、简洁、多维全面。更多云计算精华知识尽在眼前get要点、solve难题统统不在话下————— 第二天 —————小灰的思路如下第一步利用迪杰斯特拉算法的距离表求出从顶点A出发到其他各个顶点的最短距离第二步继续使用迪杰斯特拉算法求出从顶点B出发到其他各个顶点的最短距离。第三步从顶点C出发到各个顶点的最短距离。第四步从顶点D出发.............就像这样一直遍历到顶点G。这个思路的时间复杂度是多少呢假如图中有n个顶点如果不考虑堆优化一次迪杰斯特拉算法的时间复杂度是On^2。所以把每一个顶点都计算一遍总的时间复杂度是On^3。————————————举一个栗子上图的顶点A和顶点C没有直接相连的边它们之间的直接距离是无穷大。如果以B作为“中继顶点”此时A到C的最短路径就是A-B-C最短距离是325。再举一个栗子上图的顶点A和顶点C直接相连距离是6。但是存在一条“迂回”路径A-B-C距离是3256。所以经过中继顶点B从A到C的最短距离可以是5。下面我们来看一看Floyd算法的详细步骤。1.要实现Floyd算法首先需要构建带权图的邻接矩阵在邻接矩阵当中每一个数字代表着从某个顶点到另一个顶点的直接距离这个距离是没有涉及到任何中继顶点的。2.此时假定只允许以顶点A作为中继顶点那么各顶点之间的距离会变成什么样子呢B和C之间的距离原本是无穷大此时以A为中继距离缩短为AB距离AC距离527。更新对应矩阵元素橙色区域代表顶点A到其他顶点的临时距离3.接下来以顶点A、B作为中继顶点那么各顶点之间的距离会变成什么样子呢A和D之间的距离原本是无穷大此时以B为中继距离缩短为AB距离BD距离516。A和E之间的距离原本是无穷大此时以B为中继距离缩短为AB距离BE距离5611。更新对应矩阵元素橙色区域代表顶点B到其他顶点的临时距离4.接下来以顶点A、B、C作为中继顶点那么各顶点之间的距离会变成什么样子呢A和F之间的距离原本是无穷大此时以C为中继距离缩短为AC距离CF距离2810。更新对应矩阵元素橙色区域代表顶点C到其他顶点的临时距离..................以此类推我们不断引入新的中继顶点不断刷新矩阵中的临时距离。最终当所有顶点都可以作为中继顶点时我们的距离矩阵更新如下此时矩阵中每一个元素都对应着某顶点到另一个顶点的最短距离。为什么这么说呢让我们回顾一下动态规划的两大要素问题的初始状态问题的状态转移方程式对于寻找图的所有顶点之间距离的问题初始状态就是顶点之间的直接距离也就是邻接矩阵。而问题的状态转移方程式又是什么呢假设新引入的中继顶点是n那么顶点i 到 顶点j 的新距离 Min顶点i 到 顶点j 的旧距离顶点i 到 顶点n 的距离顶点n 到 顶点j 的距离final static int INF Integer.MAX_VALUE;public static void floyd(int[][] matrix){ //循环更新矩阵的值 for(int k0; kmatrix.length; k){ for(int i0; imatrix.length; i){ for(int j0; jmatrix.length; j){ if(matrix[i][k] INF || matrix[k][j] INF) { continue; } matrix[i][j] Math.min(matrix[i][j], matrix[i][k] matrix[k][j]); } } } // 打印floyd最短路径的结果 System.out.printf(最短路径矩阵: \n); for (int i 0; i matrix.length; i) { for (int j 0; j matrix.length; j) System.out.printf(%3d , matrix[i][j]); System.out.printf(\n); }}public static void main(String[] args) { int[][] matrix { {0, 5, 2, INF, INF, INF, INF}, {5, 0, INF, 1, 6, INF, INF}, {2, INF, 0, 6, INF, 8, INF}, {INF, 1, 6, 0, 1, 2, INF}, {INF, 6, INF, 1, 0, INF, 7}, {INF, INF, 8, 2, INF, 0, 3}, {INF, INF, INF, INF, 7, 3, 0} }; floyd(matrix);}福利扫描添加小编微信备注“姓名公司职位”加入【云计算学习交流群】和志同道合的朋友们共同打卡学习推荐阅读太形象了什么是边缘计算最有趣的解释没有之一互联网出海十年华为员工年薪 200 万真相让人心酸天才程序员25 岁进贝尔实验室32 岁创建信息论 琥珀 极客宝宝 5天前安全顾问反水成黑客, 靠瞎猜盗得5000万美元的以太币, 一个区块链大盗的另类传奇人造器官新突破美国科学家3D打印出会“呼吸”的肺 | Science真香朕在看了
