ディックストラ(Dijkstra)アルゴリズムは1つの頂点から残りの各頂点までの最短経路を求めます

卑屈にならないで、実力のインターネット業界を向上させて、誰が技術の牛で、誰がお父さんならば文章はあなたにエネルギーをもたらすことができて、それは最も良いことです!自分を信じて頑張ってくださいo~
1、ディクストラ(Dijkstra)アルゴリズム
ディケストラ(Dijkstra)アルゴリズムを用いて、単一ソース最短パスアルゴリズムと呼ばれる、重みマップ(すべての重み値が正数)のうちの1つの頂点から残りの各頂点への最短パスを求めることができる.
2、設計思想
アクセスした要素をvisit配列でマークし、visit【j】=1でアクセスしたことを示す.dist【j】は、ソース点vから頂点jまでの現在の最短経路長を保存するために使用され、彼の初期値はvの隣接点の重み値である.path【j】は、ソース点vからjまでの最短経路長を保存するために用いられるが、実際には、path【j】は、ソース点vから頂点jまでの現在の最短経路における頂点jの前の頂点の番号を保存し、その初期値はソース点(エッジがある場合)vの番号または−1(エッジがない場合)である.
以下のコードは以下のコードのみを参照してください.以下のコードのみを参照してください.

/**
 *  ：   
 *2020 11 23 ,  19:19
 */
import org.omg.CORBA.INTERNAL;

import java.io.IOException;
import java.util.Scanner;

public class MatrixUDG {
     

    private char[] mVexs;
    private int[][] mMatrix;
    private int num;

    public MatrixUDG(char[] vexs, char[][] edges) {
     

        num = vexs.length;

        mVexs = new char[num];
        for (int i = 0; i < mVexs.length; i++)
            mVexs[i] = vexs[i];

        mMatrix = new int[num][num];
        for(int i=0;i<num;i++){
     
            for(int j=0;j<num;j++){
     
                if(edges[i][j]=='∞'){
     
                    mMatrix[i][j]=Integer.MAX_VALUE;
                }else{
     
                    mMatrix[i][j]=Integer.parseInt(edges[i][j]+"");
                }
            }
        }
    }

    public void print() {
     
        System.out.printf("Martix Graph:
");
        for (int i = 0; i < mVexs.length; i++) {
     
            for (int j = 0; j < mVexs.length; j++){
     
                if(mMatrix[i][j]<Integer.MAX_VALUE){
     
                    System.out.printf("%d ", mMatrix[i][j]);
                }else{
     
                    System.out.print("∞ ");
                }
            }
            System.out.printf("
");
        }
    }

    public void Dijkstra(int v){
     
        int[] dist=new int[1000];
        int[] path=new int[1000];
        int[] visit=new int[1000];
        int min=Integer.MAX_VALUE;
        int k=0;
        for(int i=0;i<this.num;i++){
     
            dist[i]=this.mMatrix[v][i];
            visit[i]=0;
            if(this.mMatrix[v][i]<Integer.MAX_VALUE){
     
                path[i]=v;
            }
            else{
     
                path[i]=-1;
            }
        }
        visit[v]=1;
        for(int i=0;i<this.num;i++){
     
            min=Integer.MAX_VALUE;
            for(int j=0;j<this.num;j++){
     
                if(visit[j]==0&&dist[j]<min){
     
                    min=dist[j];
                    k=j;
                }
            }
            visit[k]=1;
            for(int j=0;j<this.num;j++){
     
                if(visit[j]==0){
     
                    if(this.mMatrix[i][j]<Integer.MAX_VALUE&&dist[k]+this.mMatrix[k][j]<dist[j]){
     
                        dist[j]=dist[k]+this.mMatrix[k][j];
                        path[j]=k;
                    }
                }
            }
        }
    }


    public static void main(String[] args) {
     

        char[] vexs={
     '0','1','2','3','4','5'};
        char[][] edges=new char[][]{
     
                {
     '0','6','1','5','∞','∞'},
                {
     '6','0','5','∞','3','∞'},
                {
     '1','5','0','5','6','4'},
                {
     '5','∞','5','0','∞','2'},
                {
     '∞','3','6','∞','0','6'},
                {
     '∞','∞','4','2','6','0'},
        };
        MatrixUDG g=new MatrixUDG(vexs,edges);
        g.print();
    }
}