图的实现与Dijkstra

import java.util.*;

import javax.swing.*;
import java.security.PublicKey;

public class GraphL {
    //顶点数组
    GraphNode node[];
    //定点数量，边数量
    int nodeNum, edgesNum;


    public static void main(String[] args) {
        GraphL gl = new GraphL();
        gl.initGraph(gl);
        System.out.println(gl.nodeNum);
    }

    public void initGraph(GraphL g) {
        //图的结点与边信息
        Graph gh = new Graph();
        int[][] adjArr = gh.setArray();

        g.node = new GraphNode[adjArr.length];
        g.nodeNum = adjArr.length;
        //结点数组初始化
        for (int i = 0; i < adjArr.length; i++) {

            GraphNode gl = new GraphNode();
            //结点数据
            gl.data = "Tom" + i;
            //结点序号
            gl.adjvex = i;
            g.node[i] = gl;
        }
        //结点邻接边初始化
        for (GraphNode gn : g.node) {
            GraphNode p = gn;
            for (int i = 0; i < g.nodeNum; i++) {
                if (adjArr[gn.adjvex][i] == 1) {
                    GraphNode newnode = new GraphNode();
                    newnode.data = g.node[i].data;
                    newnode.adjvex = i;
                    p.firstedge = newnode;
                    p = p.firstedge;
                }
                p.firstedge = null;
            }

        }
    }
}



public class Dijkstra {
    public static void main(String[] args) {
        int MaxSize = 1000001;
        //初始化一张图
        Graph g = new Graph();
        int[][] a = new int[5][5];
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++)
                a[i][j] = MaxSize;
            a[i][i] = 0;
        }

        a[0][1] = 5;
        a[0][2] = 2;
        a[0][3] = 6;
        a[1][4] = 1;
        a[2][1] = 1;
        a[2][4] = 5;
        a[2][3] = 3;
        a[3][4] = 2;
        g.initGraph(g, a);
        Dijkstra s = new Dijkstra();
        s.dijkstra(0, a);

    }

    int[] Dijkstra(Graph g, int start) {
        //已经计算完成的结点
        Stack<Integer> visited = new Stack<>();
        //等待计算的结点
        visited.push(start);
        //距离数组
        int d[] = new int[g.nodeNum];
        for (int i = 0; i < g.nodeNum; i++) {
            d[i] = 10000000;
        }
        d[0] = 0;
        //路径
        Queue<Integer> path = new LinkedList<>();
        path.offer(start);


        Queue<Integer> waiting = new LinkedList<>();

        for (int n : g.node) {
            if (n != start)
                waiting.offer(n);
        }
        while (visited.size() != g.nodeNum && waiting.size() != 0) {
            int temp[] = new int[g.nodeNum];

            for (int n : waiting) {
                System.out.println(visited.peek());
                System.out.println(n);
                temp[n] = g.arc[visited.peek()][n];
                if (d[n] > temp[n]) {
                    d[n] = temp[n];
                }
            }
            int minN = waiting.peek();
            int minD = g.arc[visited.peek()][minN];
            for (int i = 0; i < temp.length; i++) {
                if (minD < temp[i]) {
                    minD = temp[i];
                    minN = i;
                }
            }
            visited.add(minN);
            waiting.remove(minN);
            path.offer(minN);
        }
        return d;
    }

    public void dijkstra(int p, int[][] a) {
        int n = a.length;
        //存放距离
        int[] d = new int[n];
        //存放已经访问过的节点
        Set<Integer> set = new HashSet<>(n);
        set.add(p);
        //初始化距离数组，默认为直达初始点的边的权重
        for (int i = 0; i < n; i++) {
            d[i] = a[p][i];
        }
        //循环终止条件为所有结点都被访问
        while (set.size() < n) {

            int le = Integer.MAX_VALUE;
            int num = 0;
            for (int i = 0; i < n; i++) {
                //找出没被访问且距离初始点最近的点，记录距离le以及序号num
                if (!set.contains(i) && le > d[i]) {
                    le = d[i];
                    num = i;
                }
            }
            for (int i = 0; i < n; i++) {
                if (!set.contains(i)) {
                    //更新最短距离数组，判断经过当前结点到达起点与直达起点哪个更近
                    d[i] = Math.min(d[i], d[num] + a[num][i]);
                }
            }

            //距离最近的点标记为以访问
            set.add(num);
        }
        for (int i = 0; i < n; i++) {
            System.out.println("点" + p + "到点" + i + "的距离为：" + d[i]);
        }
    }

}