图的存储、创建、遍历、求最小生成树、最短路径（Java）

带权无向图

存储结构

存储结构选用邻接表。

当一个图为稀疏图时，使用邻接矩阵法显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。

当然，即使我们所处理的图不是稀疏图，邻接表法也是能够胜任的。

图、顶点以及边的代码定义

public class graph_t {
    //邻接表实现的带权无向图
    private ArrayList<VNode> vertices; //邻接表
    private int vexNum; //顶点数目
    private int arcNum = 0; //边数目
    private static boolean[] visited;

    public graph_t() {
        this.setVertices(new ArrayList<VNode>());
    }
    public graph_t(int vexNum) {
        this.vexNum = vexNum;
        this.setVertices(new ArrayList<VNode>());
    }
    //还有一些getter和setter就不赘述了
}

class ArcNode{
    //边表节点
    VNode node1;    //node1,node2为无向边连接的两个顶点
    VNode node2;
    int weight; //权值
    ArcNode next;   //指向下一条边的指针
    public  ArcNode() {}
    public ArcNode(VNode node1, VNode node2, int weight) {
        this.node1 = node1;
        this.node2 = node2;
        this.weight = weight;
        this.next = null;
    }

    public ArcNode(ArcNode node){
        this.node1 = node.node1;
        this.node2 = node.node2;
        this.weight = node.weight;
        this.next = node.next;
    }
    @Override
    public String toString() {
        return "("+this.getNode1().getName()+","+this.getWeight()+","+this.getNode2().getName()+")";
    }
}

class VNode{
    //顶点表节点
    String name;    //顶点名称
    ArcNode first;  //指向与该顶点连接的第一条边

    public VNode() {}

    public VNode(String name) {
        this.name = name;
        this.first = null;
    }
}

怎样创建图？

由于是控制台应用，所以我选择创建图的方法自然是通过用户从键盘输入。具体为以下步骤：

输入图的顶点个数；
输入图的边个数；
输入各个顶点的名称，在一行内输入，以空格分隔。例如：有四个顶点，做如下输入：A B C D；
依次输入各条边的信息，具体做法是：有几条边就输入几行信息，每行表示一条边，以这种形式"A 5 B"来表示一条边,其表示这条边连接A,B两个顶点，权值为5.

实现代码

    public void create(){
        //以用户输入方式构造图
        Scanner scanner = new Scanner(System.in);
        int vexNumIn = this.vexNum;
        int arcNumIn = this.arcNum;
        if(this.vexNum == 0){
            System.out.print("请输入顶点个数:");
            vexNumIn = scanner.nextInt();
            System.out.print("请输入边的个数:");
            arcNumIn = scanner.nextInt();
            scanner.nextLine();
        }
        System.out.println("请输入" + vexNumIn + "个顶点的名称，以空格分隔:");
        String tmpStr = scanner.nextLine();     //临时字符串
        String[] tmpDatas = tmpStr.split(" ");  //临时数据列表
        for (int i = 0; i < vexNumIn; i++) {
            this.addNode(new VNode(tmpDatas[i]));
        }
        System.out.println("请输入" + arcNumIn + "条边的数据，每条占一行，形如: a b 5, 其中a为顶点1，b为顶点2，5为权值:");
        int tmpCount = 0;   //保存一个临时数据，表示当前已输入了几条边
        while (tmpCount < arcNumIn){
            tmpStr = scanner.nextLine();
            tmpDatas = tmpStr.split(" ");
            if(this.containVnode(tmpDatas[0]) >= 0&&this.containVnode(tmpDatas[1]) >= 0){
                //当该边连接的两个顶点都存在时才能添加边
                this.addArc(new ArcNode(this.getVNodeByName(tmpDatas[0]),this.getVNodeByName(tmpDatas[1]),
                        Integer.parseInt(tmpDatas[2])));
                tmpCount ++;    //成功添加一条边，标志位加一
            }else{
                for (int k = 0; k < 2; k++) {
                    if(!(this.containVnode(tmpDatas[0]) >= 0)){
                        //为不存在的顶点给出提示信息并重新输入
                        System.out.println("不存在顶点" + tmpDatas[k] + ",请重新输入该边");
                        break;
                    }
                }
            }

        }
    }

两个辅助创建图的方法

添加顶点

向图中添加顶点非常简单，只需要将邻接表增加一项并把顶点数加一即可。

    public void addNode(VNode vnode){
        //添加顶点
        this.vertices.add(vnode);
        this.vexNum ++;
    }

添加边

向图中添加边稍难一些，因为要添加边首先要在邻接表中找到待添加边所连接的两个顶点，另外由于是无向图，所以每条边将会被添加两次，也就是在它所连接的两个顶点的边表中各出现一次。实现代码如下

    public void addArc(ArcNode arcNode){
        //添加边
        boolean isAdded = false;    //标记是否添加成功
        for (VNode node:this.vertices) {
            if(node.getName().equals(arcNode.getNode1().getName()) || node.getName().equals(arcNode.getNode2().getName())){
                //找到对应顶点
                /*这里必须复制一个arcNode的副本，不能只是简单地引用它否则有如下问题
                添加arcNode=(A,1,B)时
                匹配到A时，会改变arcNode.next的值，当在匹配到B时又会改变一次导致A的边表发生变化
                */
                ArcNode tmpArcNode = new ArcNode(arcNode);
                //头插法插入新边
                tmpArcNode.next = node.first;
                node.first = tmpArcNode;
                isAdded = true;
            }
        }
        //如果添加成功就将边数目加1
        this.arcNum = isAdded == true?this.arcNum + 1 : this.arcNum;
    }

在控制台展示图

由于直接在控制台展示图的原始形态，也就是把图画出来太过困难，于是我选择直接将图的邻接表打印在控制台上。具体的实现效果将在最后展示，实现代码如下：

    public void showGraph(){
        //展示图
        for (VNode node: this.vertices) {
            System.out.print(node.getName());
            ArcNode tmpArcNode = node.first;
            while (tmpArcNode!=null){
                System.out.print("->" + tmpArcNode.toString());
                tmpArcNode = tmpArcNode.next;
            }
            System.out.println();
        }
    }

运行效果

所执行的代码很简单：

    public static void main(String[] args) {
        graph_t g = new graph_t();
        g.create();
        g.showGraph();
    }

所输入的是这样一张图：
在这里插入图片描述
输入输出结果如下：

广度优先遍历

广度优先搜索(Breadth-First-Search,BFS) 类似于二叉树的层序遍历。基本思想是：首先访问起始顶点v，接着由v出发，依次访问未访问过的邻接顶点w1,w2,...wi,然后依次访问w1,w2,...wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问他们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时仍有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点都被访问过。

很明显每一次BFS只能遍历到一个连通分量的所有顶点，如果图不是连通图的话，一次BFS就无法遍历所有顶点了，于是为了遍历非连通图，我们引入一个辅助数组private static boolean[] visited;,visited[i]表示下标未i的顶点是否已被访问过，这样每执行完一次BFS后，检查该数组中是否还有值未false的值，如果有就从该下标开始继续BFS，如果没有则说明图已经遍历完成。

BFS代码

public ArrayList<String> BFSTraverse(){
    //对图进行广度优先遍历
    //访问标记数组初始化
    graph_t.visited = new boolean[this.vexNum];
    for (int i = 0; i < this.vexNum; i++) {
        visited[i] = false;
    }
    ArrayList<String> res = new ArrayList<>();
    for (int i = 0; i < this.vexNum; i++) {
        if(!graph_t.visited[i]){
            res =  this.BFS(i,res);
        }
    }
    return res;
}

private ArrayList<String> BFS(int vnodeIndex,ArrayList<String> tmpRes){
    //tmpRes保存临时结果，该方法执行一次只能遍历一个连通分量，需要上一个方法才能遍历整个非连通图
    //初始化辅助队列
    LinkedList<VNode> queue = new LinkedList<>();
    //讲遍历起点放入
    queue.offer(this.vertices.get(vnodeIndex));
    while (!queue.isEmpty()){
        //从队列中弹出一个顶点并访问
        VNode node = queue.remove();
        //获取该顶点的下标
        int curIndex = this.containVnode(node.getName());
        if (!graph_t.visited[curIndex]){
            //如果该店还未被访问则访问它
            graph_t.visited[curIndex] = true;
            tmpRes.add(node.getName());
            //利用临时变量遍历node的所有邻接点，并加入队列
            ArcNode tmpArcNode = new ArcNode(node.first);
            while (tmpArcNode != null){
                //小的设计缺陷，无法通过边点快速找到与node相连的顶点
                if (node.getName().equals(tmpArcNode.getNode1().getName())){
                    //此时node2试邻接点
                    queue.offer(tmpArcNode.getNode2());
                }else{
                    //否则node1为邻接点
                    queue.offer(tmpArcNode.getNode1());
                }
                tmpArcNode = tmpArcNode.next;
            }
        }
    }
    return tmpRes;
}

深度优先遍历

与广度优先搜索不同，深度优先搜索(Depth-First-Search,DFS) 类似于树的先序遍历。如其名称中所暗含的意思一样，这中搜索算法搜索策略是尽可能“深”地搜索一个图。
他的基本思想如下：首先访问图中某一起始点v，然后由v出发，访问与v邻接且未被访问任一顶点w1,再访问与w1邻接且未被访问地任一顶点w2.....重复上述过程，依次退回到最近被访问的顶点，若它还有邻接点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

一次DFS和一次BFS一样都具有不能完全遍历非连通图的问题，所有采取了和BFS相同的处理方法。

DFS代码

public ArrayList<String> DFSTraverse(){
    //对图进行深度优先遍历
    //访问标记数组初始化
    graph_t.visited = new boolean[this.vexNum];
    for (int i = 0; i < this.vexNum; i++) {
        visited[i] = false;
    }
    ArrayList<String> res = new ArrayList<>();
    for (int i = 0; i < this.vexNum; i++) {
        if(!graph_t.visited[i]){
            res =  this.DFS(i,res);
        }
    }
    return res;
}
private ArrayList<String> DFS(int vnodeIndex,ArrayList<String> tmpRes){
    //该方法与BFS思路一样只是将队列改为栈
    Stack<VNode> stack = new Stack<>();
    stack.push(this.vertices.get(vnodeIndex));
    while (!stack.isEmpty()){
        VNode node = stack.pop();
        int curIndex = this.containVnode(node.getName());
        if (!graph_t.visited[curIndex]){
            tmpRes.add(node.getName());
            graph_t.visited[curIndex] = true;
            ArcNode tmpArcNode = node.first == null ? null : new ArcNode(node.first);
            while (tmpArcNode != null){
                if (node.getName().equals(tmpArcNode.getNode1().getName())){
                    //此时node2试邻接点,精确获取当前图中的顶点对象
                    stack.push(this.getVNodeByName(tmpArcNode.getNode2().getName()));
                }else{
                    //否则node1为邻接点
                    stack.push(this.getVNodeByName(tmpArcNode.getNode1().getName()));
                }
                tmpArcNode = tmpArcNode.next;
            }
        }
    }
    return tmpRes;
}

运行结果

测试运行的代码如下：

public static void main(String[] args) {
    graph_t g = new graph_t();
    g.create();
    g.showGraph();
    System.out.println("---------------BFS-----------------------");
    ArrayList<String> bfsRes = g.BFSTraverse();
    for (int i = 0; i < g.getVexNum(); i++) {
        System.out.print(bfsRes.get(i) + " ");
    }
    System.out.println();
    System.out.println("---------------DFS-----------------------");
    ArrayList<String> dfsRes = g.DFSTraverse();
    for (int i = 0; i < g.getVexNum(); i++) {
        System.out.print(dfsRes.get(i) + " ");
    }
}

输入

输入是这样一张图：
在这里插入图片描述

输出

输出结果如下：
在这里插入图片描述

普里姆算法

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。

Prim算法构造最小生成树的过程如下图所示：

普里姆算法生成过程
初始时从图中任取一顶点（如顶点A）加入树T，此时树中只有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都加1。以此类推，直至图中所有顶点都并入T，得到的就是最小生成树。初始T必有n-1条边。

Prim算法的步骤如下：

假设G={V,E}是连通图，其最小生成树T={U,Et},Et是最小生成树中边的集合。
初始化： 向空树T={U,Et}中添加图G={V,E}的任一顶点u0，使U={u0},Et≠空集。
循环： (重复下列操作直至U=V),从图G中选择满足{(u,v)|u∈U，v∈U-V}且具有最小权值的边(u,v),加入树T，置U=U∪{v}，Et = Et∪{(u,v)}。

简单来说就是先往空树中添加任一顶点，然后把这颗树以及图去掉被添加的顶点和边剩余的部分分别视为两部分，然后不断选取连接两部分且权值最小的边，直至所有顶点都被加入树中。

代码实现

public graph_t getMSTbYPrim(){
    //普里姆算法求最小生成树
    //初始化空树
    graph_t res = new graph_t();
    //从当前图的第一个顶点开始生成
    VNode curNode = this.vertices.get(0);
    res.addNode(new VNode(curNode.getName()));
    //初始化边集合
    ArrayList<ArcNode> arcList = new ArrayList<>();
    //将添加的顶点所连接的所有边添加进边集合，后序被添加的顶点也需要此操作
    ArcNode tmpArcNode = curNode.first;
    while (tmpArcNode != null){
        arcList.add(new ArcNode(tmpArcNode));
        tmpArcNode = tmpArcNode.next;

    }
    while (res.vertices.size() < this.vertices.size()){
        //选出符合条件的边
        ArcNode curArc = this.getMinimumSpanArc(res,arcList);
        //找到新加入的顶点,根据我的设计逻辑需要先添加顶点，再添加边
        //因为每条边在添加时都会被添加两次，若先添加边，则添加时另一
        // 个顶点还不在图中，导致邻接表中每条边只出现一次(应该出现两次)
        if (res.containVnode(curArc.node1.getName()) >= 0){
            curNode = curArc.node2;
        }else{
            curNode = curArc.node1;
        }
        //加入顶点
        res.addNode(new VNode(curNode.getName()));
        //将此边加入生成树
        res.addArc(new ArcNode(curArc));
        //将添加的顶点所连接的所有边添加进边集合，后序被添加的顶点也需要此操作
        tmpArcNode = curNode.first;
        while (tmpArcNode != null){
            arcList.add(new ArcNode(tmpArcNode));
            tmpArcNode = tmpArcNode.next;
        }
    }
    return res;
}

private ArcNode getMinimumSpanArc(graph_t g,ArrayList<ArcNode> arcList){
    //prim算法的辅助函数，从边集合中选出连接res和其余顶点的权值最小的边
    ArcNode res = new ArcNode(arcList.get(0));
    //将初始权重设为极大值，否则可能出现以下情况:
    //该边不满足连接条件但是其权值比所有满足连接条件的边都小，从而导致无法找到正确的边
    res.setWeight(Integer.MAX_VALUE);
    for (ArcNode arc:arcList) {
        //两种情况，满足其一即满足连接两边的条件
        arc = new ArcNode(arc);
        boolean linked1 = g.containVnode(arc.node1.getName()) >= 0 && g.containVnode(arc.node2.getName()) < 0;
        boolean linked2 = g.containVnode(arc.node2.getName()) >= 0 && g.containVnode(arc.node1.getName()) < 0;
        if((linked1||linked2)&&arc.getWeight() < res.getWeight()){
            res = arc;
        }
    }
    //找到的同时要将此边从边集合中去除
    arcList.remove(res);
    //处理该边，使其不与其他边有联系
    res.next = null;
    return res;
}

代码主要涉及两个方法，其中public graph_t getMSTbYPrim()是Prim算法的主方法，另外一个方法private ArcNode getMinimumSpanArc(graph_t g,ArrayList<ArcNode> arcList)用来从边集合中选取符合条件的边，每次被选中的都是将被加入生成树的边。

克鲁斯卡尔算法

与Prim算法从顶点开始扩展最小生成树不同，Kruskal(克鲁斯卡尔)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

克鲁斯卡尔算法构造最小生成树的过程如下图所示：
克鲁斯卡尔算法构造过程
初始时为只有n个顶点而无边的非连通图T={V,{}},每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取且权值最小的边若该边依附的顶点落在T中不同的联通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边。以此类推，直至T中所有顶点都在一个联通分量上。

Kruskal算法的步骤如下：

假设G={V,E}是连通图，其最小生成树T={U,Et}。
初始化： U = V, Et = 空集。即每个顶点构成一棵独立的树，T此时是一个仅含|V|个顶点的森林。
循环 (重复下列操作直至T是一棵树): 按G的边的权值递增顺序依次从E-Et中选择一条边，若这条边加入T后不构成回路，则将其加入Et，否则舍弃，知道Et中含有n-1条边。

代码实现

public graph_t getMSTByKruskal(){
        //克鲁斯卡尔算法求最小生成树
        //初始化生成树
        graph_t res = new graph_t();
        //初始化边集合
        ArrayList<ArcNode> arcList = new ArrayList<>();
        //将图的所有边加入边集合
        for (VNode vnode:this.vertices) {
            ArcNode tmpArc = new ArcNode(vnode.first);
            while (tmpArc != null){
                arcList.add(tmpArc);
                tmpArc = tmpArc.next;
            }
        }
        while (res.getVexNum() < this.getVexNum() || res.getConnNum() > 1){
            //当生成树中顶点数小于图中定点数或者生成树还不是一个连通图时说明生成还未完成
            //选出满足条件的权值最小的边
            ArcNode  selectedArc = getArcForKruskal(res,arcList);
            if(res.containVnode(selectedArc.node1.getName()) < 0){
                //若顶点1未被连接则添加该顶点
                res.addNode(new VNode(selectedArc.node1.getName()));
            }
            if(res.containVnode(selectedArc.node2.getName()) < 0){
                //若顶点2未被连接则添加该顶点
                res.addNode(new VNode(selectedArc.node2.getName()));
            }
            //添加该边
            res.addArc(new ArcNode(selectedArc));
        }
        return res;
    }

private ArcNode getArcForKruskal(graph_t g,ArrayList<ArcNode> arcList){
    //克鲁斯卡尔算法的辅助函数，从边集合中选出符合条件的边
    ArcNode res = new ArcNode(arcList.get(0));
    res.setWeight(Integer.MAX_VALUE);
    for (ArcNode arc:arcList) {
        arc = new ArcNode(arc);
        //若顶点1已被连接
        boolean linked1 = g.containVnode(arc.node1.getName()) >= 0 ;
        //若顶点2已被连接
        boolean linked2 = g.containVnode(arc.node2.getName()) >= 0 ;
        if(((!(linked1&&linked2))||(!g.canReach(arc.node1,arc.node2)))&&arc.getWeight() < res.getWeight()){
            //只要不是两个顶点都已被连接或者二者不属于同一联通分量就满足连接条件
            res = arc;
        }
    }
    //找到的同时要将此边从边集合中去除
    arcList.remove(res);
    //处理该边，使其不与其他边有联系
    res.next = null;
    //不这样处理的话，该边所引用的两个顶点还是之前图中的顶点
    res.setNode1(new VNode(res.node1.getName()));
    res.setNode2(new VNode(res.node2.getName()));
    return res;
}
public boolean canReach(VNode node1,VNode node2){
    //通过dfs判断从node1出发是否能到达node2,如果能则二者属于同一连通分量，否则不属于
    //该方法与BFS思路一样只是将队列改为栈
    //访问标记数组初始化
    graph_t.visited = new boolean[this.vexNum];
    for (int i = 0; i < this.vexNum; i++) {
        visited[i] = false;
    }
    Stack<VNode> stack = new Stack<>();
    stack.push(this.vertices.get(this.containVnode(node1.getName())));
    while (!stack.isEmpty()){
        VNode node = stack.pop();
        int curIndex = this.containVnode(node.getName());
        if (!graph_t.visited[curIndex]){
//                tmpRes.add(node.getName());
            graph_t.visited[curIndex] = true;
            //如果node后面没有边,直接调用new ArcNode(node.first)会导致空指针异常
            ArcNode tmpArcNode = node.first == null ? null : new ArcNode(node.first);
            while (tmpArcNode != null){
                if (node.getName().equals(tmpArcNode.getNode1().getName())){
                    //此时node2试邻接点
                    stack.push(this.getVNodeByName(tmpArcNode.getNode2().getName()));
                }else{
                    //否则node1为邻接点
                    stack.push(this.getVNodeByName(tmpArcNode.getNode1().getName()));
                }
                tmpArcNode = tmpArcNode.next;
            }
        }
    }
    return graph_t.visited[this.containVnode(node2.getName())];
}
public int getConnNum(){
    //通过获取图的连通分量个数来判断图是否为来连通图
    //通过改造DFSTraverse方法来获取连通分量个数，DFS函数执行的次数对应着连通分量个数
    graph_t.visited = new boolean[this.vexNum];
    for (int i = 0; i < this.vexNum; i++) {
        visited[i] = false;
    }
    ArrayList<String> res = new ArrayList<>();
    int connNum = 0;
    for (int i = 0; i < this.vexNum; i++) {
        if(!graph_t.visited[i]){
            res =  this.DFS(i,res);
            //每执行一个该函数，连通分量个数加一
            connNum++;
        }
    }
    return connNum;
}

克鲁斯卡尔算法虽然逻辑上比普里姆算法更加简单清晰，但其实现起来要比普里姆算法稍难一些，主要是因为克鲁斯卡尔算法在选择边时需要判断两个顶点是否属于同一连通分量，于是我又额外添加了两个方法public int getConnNum()和private ArcNode getArcForKruskal(graph_t g,ArrayList<ArcNode> arcList),其中前者用来计算一个图中共有几个连通分量，借助它可以判断算法何时结束，后者用来判断两个顶点是否属于同一连通分量，这两个方法的实现思路都已写在注释里了。

运行效果

测试运行的代码：

public static void main(String[] args) {
    graph_t g = new graph_t();
    g.create();
    g.showGraph();
    System.out.println("---------------克鲁斯卡尔算法-----------------------");
    graph_t MST = g.getMSTByKruskal();
    MST.showGraph();
    System.out.println("---------------普里姆算法-----------------------");
    graph_t mst_p = g.getMSTbYPrim();
    mst_p.showGraph();
}

输入输出

输入图即为上面描述两种算法构造过程的图片中的带权无向图
输出结果如下：
在这里插入图片描述

迪杰斯特拉算法

迪杰斯特拉算法(Dijkstra) 是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

Dijkstra算法设置一个集合S记录已求得最短路径的顶点，初始时把源点v0放入S,
集合S每并入一个新顶点vi，都要修改源点v0到集合V-S中顶点当前的最短路径长度值。
在构造的过程中需要设置两个辅助数组：

dist[]: 记录从源点v0到其他各顶点当前的最短路径长度，它的初态为：若从v0到vi有边，则dist[i]为该边的权值；否则设置dist[i]为∞。
path[]: path[i]表示从源点到顶点i之间的最短路径的前驱结点。在算法结束时，可根据其值追溯得到源点v0到顶点vi的最短路径。

迪杰斯特拉算法的步骤如下：

初始化：集合S初始化为{0},dist[]的初值为dist[i] = getWeight(0,i),i = 1,2,3...n-1。
从顶点集合V-S中选出vi，满足dist[j] = Min{dist[i] | vi∈V-S},vj就是当前求得的一条从v0出发的最短路径的终点，领S = S ∪ {j}。
修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度：若dist[j] + getWeight(j,k) < dist[k],则更新dist[k] = dist[j] + getWeight(j,k)。
重复2~3操作共n-1次，知道所有顶点都包含在S中。

实现代码

public int[] Dijkstra(){
    //迪杰斯特拉算法求单源最短路径
    //为了方便这里我就默认从0号顶点出发，也可以将出发点改为用户输入
    //初始化集合S
    ArrayList<Integer> S = new ArrayList<>();   //S保存顶点的编号
    S.add(0);
    //初始化path数组
    int[] path = new int[this.vexNum];
    for (int i = 0; i < path.length; i++) {
        path[i] = -1;
    }
    //初始化dist数组
    int[] dist = new int[this.vexNum];
    for (int i = 0; i < this.vexNum; i++) {
        dist[i] = this.getWeight(this.vertices.get(0).getName(),this.vertices.get(i).getName());
        if(dist[i] < Integer.MAX_VALUE){
            path[i] = 0;
        }
    }

    while (S.size() < this.vexNum){
        //当集合S中的顶点数量等于图的顶点数量时，算法即可结束
        //选择符合条件的Vj，Vj就是当前求得的一条从V0出发的最短路径的重点
        int Vj = getNodeForDij(S,dist);
        S.add(new Integer(Vj));
        //修改从V0出发到集合V-S上任一顶点Vk可达的最短路径长度
        for (int k = 0; k < this.vexNum; k++) {
            if (!S.contains(k)){
                //S中不包含该顶点则说明该顶点∈V-S
                //直接这样写会导致当this.getWeight(this.vertices.get(Vj).getName(),this.vertices.get(k).getName())为
                //整数最大值时，newDist由于溢出而获得一个负值
//                    int newDistK = dist[Vj] + this.getWeight(this.vertices.get(Vj).getName(),this.vertices.get(k).getName());
                int tmpWeight = this.getWeight(this.vertices.get(Vj).getName(),this.vertices.get(k).getName());
                int newDistK =  tmpWeight == Integer.MAX_VALUE ? Integer.MAX_VALUE : dist[Vj] + tmpWeight;
                if(newDistK < dist[k]){
                    //如果V0->Vj->Vk这条路径的长度要小于我们之前记录的从V0->Vk的最短路径，那么就要更新V0->Vk的最短路径s
                    dist[k] = newDistK;
                    //并且此时Vj就是V0到Vk这条最短路径的前驱节点
                    path[k] = Vj;
                }
            }
        }
    }
    return path;
}

public int getWeight(String node1,String node2){
    //获取两个顶点之间的边的权值，如果顶点不存在或边不存在或node1和node2是同一顶点，都返回无穷
    //此处将Integer.MAX_VALUE视为正无穷
    int node1Index = this.containVnode(node1);
    if((node1Index < 0 || this.containVnode(node2) < 0)|| node1.equals(node2)){
        return Integer.MAX_VALUE;
    }
    VNode node = this.vertices.get(node1Index);
    ArcNode tmpArcNode = new ArcNode(node.first);
    while (tmpArcNode!=null){
        if(tmpArcNode.node1.getName().equals(node2) || tmpArcNode.node2.getName().equals(node2)){
            //由于我们找的是顶点node1的边表，所以无论临时边的node1还是node2与参数node2匹配都说明找到要找的边
            return tmpArcNode.weight;
        }
        tmpArcNode = tmpArcNode.next;
    }
    //如果经过循环没找到说明不存在该边
    return Integer.MAX_VALUE;
}
private int getNodeForDij(ArrayList<Integer> S, int[] dist){
    //此方法为Dijkstra算法的辅助函数，用于从顶点集合V-S中选出符合条件的顶点的下标
    int res = 0;
    for (int i = 0; i < dist.length; i++) {
        if ((!S.contains(i))&&dist[i] < dist[res]){
            res = i;
        }
    }
    return res;
}

测试运行

所运行的代码如下：

    public static void main(String[] args) {
        graph_t g = new graph_t();
        g.create();
        g.showGraph();
        int[] path = g.Dijkstra();
        System.out.println("迪杰斯特拉算法求得的path数组:");
        for (int i = 0; i < path.length; i++) {
            System.out.print(path[i] + " ");
        }
        System.out.println();
    }

输入

所输入是这样一张图：
在这里插入图片描述

输出

在这里插入图片描述

如有错误恳请指正

图的存储、创建、遍历、求最小生成树、最短路径（Java）

带权无向图

存储结构

图、顶点以及边的代码定义

怎样创建图？

实现代码

两个辅助创建图的方法

添加顶点

添加边

在控制台展示图

运行效果

广度优先遍历

BFS代码

深度优先遍历

DFS代码

运行结果

输入

输出

普里姆算法

代码实现

克鲁斯卡尔算法

代码实现

运行效果

输入输出

迪杰斯特拉算法

实现代码

测试运行

输入

输出

推荐阅读