Java实现Floyd算法求最短路径

本文实例为大家分享了Java实现Floyd算法求最短路径的具体代码，供大家参考，具体内容如下

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner; 

public class TestMainIO { 

 /**
  * @param args
  * @throws FileNotFoundException
  */
 public static void main(String[] args) throws FileNotFoundException {
  TestMainIO test_print = new TestMainIO();
  int[][] G = test_print.intputGragh("D:\\Users\\test.txt" , 6);
  int[][] Dis = test_print.floyd(G, 6);
  test_print.printG(Dis, 6);
 } 

 public void printG(int[][] G,int n){
  for(int i=0;i<n;i++){
   for(int j=0;j<n;j++){
    System.out.println(i+"->"+j+" "+G[i][j]);
   }
  }
 } 

 public int[][] intputGragh(String path , int num) throws FileNotFoundException{
  int[][] G = new int[num][num];
  for(int i=0;i<num;i++){
   for(int j=0;j<num;j++){
    G[i][j]=999;
   }
  }
  Scanner in = new Scanner(new FileInputStream(path));
  while (in.hasNext()) {
   int i = in.nextInt();
   int j = in.nextInt();
   int weight = in.nextInt();
   G[i][j] = weight;
  }
  return G;
 } 

 public int[][] floyd(int[][] G,int n){
  int[][] Dis= new int[n][n];
  for(int q=0;q<n;q++){
   for(int w=0;w<n;w++){
    Dis[q][w]=G[q][w];
   }
  } 

  for(int k = 0; k < n; k++){
   for(int i=0; i < n; i++ ){
    for(int j=0; j < n; j++){
     if(Dis[i][j]>Dis[i][k]+Dis[k][j]){
      Dis[i][j]=Dis[i][k]+Dis[k][j];
     }
    }
   }
  }
  return Dis;
 }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • java算法导论之FloydWarshall算法实现代码

    摘要: 算法导论之FloydWarshall算法 求一个图中任意两点之间的最短路径 FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径 如果普通求最短路径,可以对图进行V次(顶点数)BellmanFord算法. 这样的话时间复杂度为EV^2 如果是稀疏图,则近似于V^3 但是如果是密集图,则时间复杂度会近似达到V^4,这种情况需要优化,这里FloydWarshall通过动态规划进行优化 ,并且使用邻接矩阵来表示图. 实例代码: package org.loda.graph;

  • java实现Floyd算法

    java实现Floyd算法

    Floyd算法:用于多源最短路径的求解,算出来的是所有的节点到其余各节点之间的最短距离. 该算法的思路是:首先初始化距离矩阵,然后从第一个点开始逐渐更新矩阵点值.d[i][j]表示从i点到j点的距离.第k次更新时,判断d[i][k]+d[k][j]与d[i][j]的大小,如果前者小,则更新这个值,否则不变. 给一个例子: 具体的floyd实现算法如下[java] view plain copy package com.blyang; public class Floyd { int[][] Ma

  • Java实现Floyd算法求最短路径

    本文实例为大家分享了Java实现Floyd算法求最短路径的具体代码,供大家参考,具体内容如下 import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class TestMainIO { /** * @param args * @throws FileNotFoundException */ public static void main(Stri

  • Python基于Floyd算法求解最短路径距离问题实例详解

    本文实例讲述了Python基于Floyd算法求解最短路径距离问题.分享给大家供大家参考,具体如下: Floyd算法和Dijkstra算法,相信大家都不陌生,在最短路径距离的求解中应该算得上是最为基础和经典的两个算法了,今天就用一点时间来重新实现一下,因为本科的时候学习数据结构才开始接触的这个算法,当时唯一会用的就是C语言了,现在的话,C语言几乎已经离我远去了,个人感觉入手机器学习以来python更得我心,因为太通俗易懂了,带给你的体验自然也是非常不错的. 当然网上 有很多的算法讲解教程,我不会在

  • Java实现Floyd算法的示例代码

    Java实现Floyd算法的示例代码

    目录 一 问题描述 二 代码 三 实现 一 问题描述 求节点0到节点2的最短路径. 二 代码 package graph.floyd; import java.util.Scanner; public class Floyd { static final int MaxVnum = 100; // 顶点数最大值 static final int INF = 0x3f3f3f3f; //无穷大 static final int dist[][] = new int[MaxVnum][MaxVnum

  • C++用Dijkstra(迪杰斯特拉)算法求最短路径

    C++用Dijkstra(迪杰斯特拉)算法求最短路径

    算法介绍 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低. 算法思想 按路径长度递增次序产生算法: 把顶点集合V分成两组: (1)S:已求出的顶点的集合(初始时只含有源点V0) (2)V-S=T:尚未确定的顶点集合 将T中顶点按递增

  • Java Floyd算法求有权图（非负权）的最短路径并打印

    状态转移方程:d(i,j) = min(d(i,j),d(i,k)+d(k,j)),其中i<k<j 思路对于每一个k(i<k<j),全部遍历下来之后,肯定会发生一次有效的比较 public class FloydTest { private static int[][] matrix; private static int[][] path; public static void main(String[] args) { initMatrixAndPath( new int[][

  • Java利用Dijkstra和Floyd分别求取图的最短路径

    Java利用Dijkstra和Floyd分别求取图的最短路径

    目录 1 最短路径的概述 2 杰斯特拉(Dijkstra)算法 2.1 原理 2.2 案例分析 3 弗洛伊德(Floyd)算法 3.1 原理 3.2 案例分析 4 邻接矩阵加权图实现 5 邻接表加权图实现 本文详细介绍了图的最短路径的概念,然后介绍了求最短路径的两种算法:Dijkstra算法和Floyd算法的原理,最后提供了基于邻接矩阵和邻接表的图对两种算法的Java实现. 阅读本文需要一定的图的基础,如果对于图不是太明白的可以看看这篇文章:Java数据结构之图的原理与实现. 1 最短路径的概述

  • C++求所有顶点之间的最短路径（用Floyd算法）

    C++求所有顶点之间的最短路径（用Floyd算法）

    本文实例为大家分享了C++所有顶点之间最短路径的具体代码,供大家参考,具体内容如下 一.思路: 不能出现负权值的边 用Floyd算法,总的执行时间为O(n的3次方) k从顶点0一直到顶点n-1, 如果,有顶点i到顶点j之间绕过k,使得两顶点间的路径更短,即dist[i][k] + dist[k][j] < dist[i][j],则修改:dist[i][j] 如:(1)当k=0时, 顶点2绕过顶点0到达顶点1,使得路径为:3+1 < dist[2][1],所以,要修改dist[2][1]=4,同

  • java图论弗洛伊德和迪杰斯特拉算法解决最短路径问题

    java图论弗洛伊德和迪杰斯特拉算法解决最短路径问题

    目录 弗洛伊德算法 算法介绍 算法图解分析   迪杰斯特拉算法 算法介绍 算法过程  弗洛伊德算法 算法介绍 算法图解分析     第一轮循环中,以A(下标为:0)作为中间顶点 [即把作为中间顶点的所有情况都进行遍历,就会得到更新距离表和前驱关系],距离表和前驱关系更新为: 弗洛伊德算法和迪杰斯特拉算法的最大区别是: 弗洛伊德算法是从各个顶点出发,求最短路径: 迪杰斯特拉算法是从某个顶点开始,求最短路径. /** * 弗洛伊德算法 * 容易理解,容易实现 */ public void floyd

  • C++实现多源最短路径之Floyd算法示例

    本文实例讲述了C++实现多源最短路径之Floyd算法.分享给大家供大家参考,具体如下: #include<cstdio> #include<cstring> #include<iostream> #define MAX 999 using namespace std; int n,m; int e[MAX][MAX]; void Init() { for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) { if(i==

随机推荐