Java实现Dijkstra算法的示例代码

目录
  • 一 问题描述
  • 二 实现
  • 三 测试

一 问题描述

小明为位置1,求他到其他各顶点的距离。

二 实现

package graph.dijkstra;

import java.util.Scanner;
import java.util.Stack;

public class Dijkstra {
    static final int MaxVnum = 100;  // 顶点数最大值
    static final int INF = 0x3f3f3f3f; //无穷大
    static final int dist[] = new int[MaxVnum]; // 最短距离
    static final int p[] = new int[MaxVnum]; // 前驱数组
    static final boolean flag[] = new boolean[MaxVnum]; // 如果 s[i] 等于 true,说明顶点 i 已经加入到集合 S ;否则顶点 i 属于集合 V-S

    static int locatevex(AMGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标
            if (x == G.Vex[i])
                return i;
        return -1; // 没找到
    }

    static void CreateAMGraph(AMGraph G) {
        Scanner scanner = new Scanner(System.in);
        int i, j;
        char u, v;
        int w;
        System.out.println("请输入顶点数:");
        G.vexnum = scanner.nextInt();
        System.out.println("请输入边数:");
        G.edgenum = scanner.nextInt();
        System.out.println("请输入顶点信息:");

        // 输入顶点信息,存入顶点信息数组
        for (int k = 0; k < G.vexnum; k++) {
            G.Vex[k] = scanner.next().charAt(0);
        }
        //初始化邻接矩阵所有值为0,如果是网,则初始化邻接矩阵为无穷大
        for (int m = 0; m < G.vexnum; m++)
            for (int n = 0; n < G.vexnum; n++)
                G.Edge[m][n] = INF;

        System.out.println("请输入每条边依附的两个顶点及权值:");
        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);
            w = scanner.nextInt();

            i = locatevex(G, u);// 查找顶点 u 的存储下标
            j = locatevex(G, v);// 查找顶点 v 的存储下标
            if (i != -1 && j != -1)
                G.Edge[i][j] = w; //有向图邻接矩阵
            else {
                System.out.println("输入顶点信息错!请重新输入!");
                G.edgenum++; // 本次输入不算
            }
        }
    }

    static void print(AMGraph G) { // 输出邻接矩阵
        System.out.println("图的邻接矩阵为:");
        for (int i = 0; i < G.vexnum; i++) {
            for (int j = 0; j < G.vexnum; j++)
                System.out.print(G.Edge[i][j] + "\t");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AMGraph G = new AMGraph();
        int st;
        char u;
        CreateAMGraph(G);
        System.out.println("请输入源点的信息:");
        Scanner scanner = new Scanner(System.in);
        u = scanner.next().charAt(0);
        ;
        st = locatevex(G, u);//查找源点u的存储下标
        Dijkstra(G, st);
        System.out.println("小明所在的位置:" + u);

        for (int i = 0; i < G.vexnum; i++) {
            System.out.print("小明:" + u + " - " + "要去的位置:" + G.Vex[i]);

            if (dist[i] == INF)
                System.out.print(" sorry,无路可达");
            else
                System.out.println(" 最短距离为:" + dist[i]);
        }
        findpath(G, u);
    }

    public static void Dijkstra(AMGraph G, int u) {
        for (int i = 0; i < G.vexnum; i++) {
            dist[i] = G.Edge[u][i]; //初始化源点u到其他各个顶点的最短路径长度
            flag[i] = false;
            if (dist[i] == INF)
                p[i] = -1; //源点u到该顶点的路径长度为无穷大,说明顶点i与源点u不相邻
            else
                p[i] = u; //说明顶点i与源点u相邻,设置顶点i的前驱p[i]=u
        }
        dist[u] = 0;
        flag[u] = true;   //初始时,集合S中只有一个元素:源点u
        for (int i = 0; i < G.vexnum; i++) {
            int temp = INF, t = u;
            for (int j = 0; j < G.vexnum; j++) //在集合V-S中寻找距离源点u最近的顶点t
                if (!flag[j] && dist[j] < temp) {
                    t = j;
                    temp = dist[j];
                }
            if (t == u) return; //找不到t,跳出循环
            flag[t] = true;  //否则,将t加入集合
            for (int j = 0; j < G.vexnum; j++)//更新V-S中与t相邻接的顶点到源点u的距离
                if (!flag[j] && G.Edge[t][j] < INF)
                    if (dist[j] > (dist[t] + G.Edge[t][j])) {
                        dist[j] = dist[t] + G.Edge[t][j];
                        p[j] = t;
                    }
        }
    }

    public static void findpath(AMGraph G, char u) {
        int x;
        Stack<Integer> S = new Stack<>();
        System.out.println("源点为:" + u);

        for (int i = 0; i < G.vexnum; i++) {
            x = p[i];
            if (x == -1 && u != G.Vex[i]) {
                System.out.println("源点到其它各顶点最短路径为:" + u + "--" + G.Vex[i] + "    sorry,无路可达");
                continue;
            }
            while (x != -1) {
                S.push(x);
                x = p[x];
            }
            System.out.println("源点到其它各顶点最短路径为:");
            while (!S.empty()) {
                System.out.print(G.Vex[S.peek()] + "--");
                S.pop();
            }
            System.out.println(G.Vex[i] + "    最短距离为:" + dist[i]);
        }
    }
}

class AMGraph {
    char Vex[] = new char[Dijkstra.MaxVnum];
    int Edge[][] = new int[Dijkstra.MaxVnum][Dijkstra.MaxVnum];
    int vexnum; // 顶点数
    int edgenum; // 边数
}

三 测试

到此这篇关于Java实现Dijkstra算法的示例代码的文章就介绍到这了,更多相关Java Dijkstra算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java实现最短路径算法之Dijkstra算法

    前言 Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法.该算法被称为是"贪心算法"的成功典范.本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予java实现代码. 一.知识准备: 1.表示图的数据结构 用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵. 图的邻接矩阵存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息. 设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: 从上面可以看出,无

  • 详解Java中Dijkstra(迪杰斯特拉)算法的图解与实现

    目录 简介 工作过程 总体思路 实现 小根堆 Dijsktra 测试 简介 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等.注意该算法要求图中不存在负权边.对应问题:在无向图G=(V,E)中,假设每条边E(i)的长度W(i),求由顶点V0到各节点的最短路径. 工作过

  • 教你在 Java 中实现 Dijkstra 最短路算法的方法

    目录 定义 带权有向图的实现 带权有向边 带权有向图 最短路算法 API Dijkstra 算法 算法流程 最小索引优先队列 实现算法 后记 定义 最短路问题的定义为: 下图左侧是一幅带权有向图,以顶点 0 为起点到各个顶点的最短路径形成的最短路径树如下图右侧所示: 带权有向图的实现 在实现最短路算法之前需要先实现带权有向图.在上一篇博客 <如何在 Java 中实现最小生成树算法> 中我们实现了带权无向图,只需一点修改就能实现带权有向图. 带权有向边 首先应该实现带权有向图中的边 Direct

  • java实现dijkstra最短路径寻路算法

    [引用]迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径. 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止. 基本思想 通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算). 此外,引进两个集合S和U.S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离). 初始时,S中只有起点s:U中是除s之外的顶点,并且U中顶点的路径是

  • java实现Dijkstra算法

    本文实例为大家分享了java实现Dijkstra算法的具体代码,供大家参考,具体内容如下 1 问题描述 何为Dijkstra算法? Dijkstra算法功能:给出加权连通图中一个顶点,称之为起点,找出起点到其它所有顶点之间的最短距离. Dijkstra算法思想:采用贪心法思想,进行n-1次查找(PS:n为加权连通图的顶点总个数,除去起点,则剩下n-1个顶点),第一次进行查找,找出距离起点最近的一个顶点,标记为已遍历:下一次进行查找时,从未被遍历中的顶点寻找距离起点最近的一个顶点, 标记为已遍历:

  • 基于Java实现的Dijkstra算法示例

    本文以实例形式介绍了基于Java实现的Dijkstra算法,相信对于读者研究学习数据结构域算法有一定的帮助. Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法.即先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止. 其代码实现如下所示: package com.algorithm.impl; public class Dijkstra { private static int M =

  • java实现Dijkstra最短路径算法

    任务描述:在一个无向图中,获取起始节点到所有其他节点的最短路径描述 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止. Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表方式 用OPEN,CLOSE表的方式,其采用的是贪心法的算法策略,大概过程如下: 1.声明两个集合,open和close,open用于存储未遍历的节点,close用来存储

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

    目录 一 问题描述 二 实现 三 测试 一 问题描述 小明为位置1,求他到其他各顶点的距离. 二 实现 package graph.dijkstra; import java.util.Scanner; import java.util.Stack; public class Dijkstra { static final int MaxVnum = 100; // 顶点数最大值 static final int INF = 0x3f3f3f3f; //无穷大 static final int

  • Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    目录 1.查找概述 2.顺序查找 3.二分查找 3.1 二分查找概述 3.2 二分查找实现 4.插值查找 4.1 插值查找概述 4.2 插值查找实现 5.斐波那契查找 5.1 斐波那契查找概述 5.2 斐波那契查找实现 5.3 总结 1.查找概述 查找表: 所有需要被查的数据所在的集合,我们给它一个统称叫查找表.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合. 查找(Searching): 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录).

  • Java实现雪花算法的示例代码

    一.介绍 SnowFlow算法是Twitter推出的分布式id生成算法,主要核心思想就是利用64bit的long类型的数字作为全局的id.在分布式系统中经常应用到,并且,在id中加入了时间戳的概念,基本上保持不重复,并且持续一种向上增加的方式. 在这64bit中,其中``第一个bit是不用的,然后用其中的41个bit作为毫秒数,用10bit作为工作机器id,12bit`作为序列号.具体如下图所示: 第一个部分:0,这个是个符号位,因为在二进制中第一个bit如果是1的话,那么都是负数,但是我们生成

  • Java实现抽奖算法的示例代码

    目录 一.题目描述 二.解题思路 三.代码详解 四.优化抽奖算法 解题思路 代码详解 一.题目描述 题目: 小虚竹为了给粉丝送福利,决定在参与学习打卡活动的粉丝中抽一位幸运粉丝,送份小礼物.为了公平,要保证抽奖过程是随机的. 二.解题思路 1.把参与的人员加到集合中 2.使用Random对象获取随机数 3.把随机数当下标,获取集合中的幸运用户 三.代码详解 public class Basics28 { public static void main(String[] args) { List<

  • 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

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

    目录 介绍 一.构建后的图 二.代码 三.测试 介绍 构造最小生成树还有一种算法,即 Kruskal 算法:设图 G=(V,E)是无向连通带权图,V={1,2,...n};设最小生成树 T=(V,TE),该树的初始状态只有 n 个节点而无边的非连通图T=(V,{}),Kruskal 算法将这n 个节点看成 n 个孤立的连通分支.它首先将所有边都按权值从小到大排序,然后值要在 T 中选的边数不到 n-1,就做这样贪心选择:在边集 E 中选择权值最小的边(i,j),如果将边(i,j)加入集合 TE

  • C++实现Dijkstra算法的示例代码

    目录 一.算法原理 二.具体代码 1.graph类 2.PathFinder类 3. main.cpp 三.示例 一.算法原理 链接: Dijkstra算法及其C++实现参考这篇文章 二.具体代码 1.graph类 graph类用于邻接表建立和保存有向图. graph.h: #ifndef GRAPH_H #define GRAPH_H #include <iostream> #include <string> #include <vector> #include &l

  • Java实现8种排序算法的示例代码

    冒泡排序 O(n2) 两个数比较大小,较大的数下沉,较小的数冒起来. public static void bubbleSort(int[] a) { //临时变量 int temp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for (int i = 0; i < a.length; i++) { //从最后向前面两两对比,j是比较中下标大的值 for (int j = a.length - 1; j > i; j--) { //让小的数字排在前面 if (a[j] <

  • JAVA用递归实现全排列算法的示例代码

    求一个n阶行列式,一个比较简单的方法就是使用全排列的方法,那么简述以下全排列算法的递归实现. 首先举一个简单的例子说明算法的原理,既然是递归,首先说明一下出口条件.以[1, 2]为例 首先展示一下主要代码(完整代码在后面),然后简述 //对数组array从索引为start到最后的元素进行全排列 public void perm(int[]array,int start) { if(start==array.length) { //出口条件 for(int i=0;i<array.length;i

随机推荐