菜单
  

    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之间的最短路径

    胜利乡有7个村庄(A, B, C, D, E, F, G)

    各个村庄的距离用边线表示(权) ,比如 A – B 距离 5公里

    问:如何计算出各村庄到 其它各村庄的最短距离?论文网

    思路

    设置顶点vi到顶点vk的最短路径已知为Lik,顶点vk到vj的最短路径已知为Lkj,顶点vi到vj的路径为Lij,则vi到vj的最短路径为:min((Lik+Lkj),Lij),vk的取值为图中所有顶点,则可获得vi到vj的最短路径

    至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj,是以同样的方式获得

    package com.atguigu.floyd;

     

    import java.util.Arrays;

     

    public class FloydAlgorithm {

     

        public static void main(String[] args) {

            char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };

            int[][] matrix = new int[vertex.length][vertex.length];

            final int N = 65535;

            matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 };

            matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 };

            matrix[2] = new int[] { 7, N, 0, N, 8, N, N };

            matrix[3] = new int[] { N, 9, N, 0, N, 4, N };

            matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 };

            matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 };

            matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };

            

            Graph graph = new Graph(vertex.length, matrix, vertex);

            graph.floyd();

            graph.show();

        }

     

    }

     

     

    class Graph {

        private char[] vertex; 

        private int[][] dis;

        private int[][] pre;

        

        public Graph(int length, int[][] matrix, char[] vertex) {

            this.vertex = vertex;

            this.dis = matrix;

            this.pre = new int[length][length];

            for (int i = 0; i < length; i++) {

                Arrays.fill(pre[i], i);

            }

        }

     

        public void show() {

            char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };

            for (int k = 0; k < dis.length; k++) {

                for (int i = 0; i < dis.length; i++) {

                    System.out.print(vertex[pre[k][i]] + " ");

                }

  1. 上一篇:什么是软件包的依赖关系
  2. 下一篇:求一个网站你懂的网站
  1. 车险市场研究开题报告

  2. 公允价值计量的探究+文献综述

  3. DCF模型在会计实务和投资评价中缺陷分析

  4. 小学英语课堂气氛与教学效率的相关性研究

  5. 果糖脱水制备HMF的研究现状和参考文献

  6. 深圳福特汽车4S店服务营销策略研究

  7. K60单片机基于舵机的简易...

  8. 污水处理工艺氧化沟英文文献和中文翻译

  9. 论刘震云小说《一句顶一万句》的艺术特色

  10. 从人本主义视角论小学生学习英语动机的培养

  

About

优尔论文网手机版...

主页:http://www.youerw.com

关闭返回