单源最短路径（Dijkstra算法详解&&Java实现）

算法过程

Code

Input

Output

在寻找加权无向图中的最小生成树的Prim算法：构造最小生成树每一步都向这棵树中添加一条新的边。Dijkstra算法采用了类似的方法计算最短路径树。

关于Prim算法可点击下方链接进行了解。

Prim算法

算法过程

这里我们以3为源点出发,这里的顶点同意表示为vi（顶点3表示v3)：

同时把v3标记为已经使用过

 按照此步骤局部进行：

 与下方的输出结合观察，更能直观的了解其过程：

Code

import java.util.*;
import java.io.*;

public class Dijkstra {
    public static final int INF=1000;//定义一个无限距离,当两个顶点之间不存在连接且无权值设置为INF
    public static int V;//顶点个数
    public static int cost[][];//cost[v][u]表示从顶点v到顶点u的权值
    public static boolean used[];//顶点是否已被使用
    public static int d[];//从一个顶点v出发的最短距离
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        while (in.hasNext()) {
            V=in.nextInt();
            System.out.println("Vertex number: "+V);//顶点个数
            //初始化
            cost=new int[V][V];
            used=new boolean[V];
            d=new int[V];
            for (int i = 0; i < V; i++) {
                Arrays.fill(cost[i],INF);
            }
            //输入数据
            //顶点之间的边赋值 输入为0 0 0 时退出
            while (true){
                int v0=in.nextInt();//顶点1
                int v1=in.nextInt();//顶点2
                int c=in.nextInt();//顶点之间权值
                if(v0==0&&v1 == 0&&c == 0){
                    System.out.println("Done");
                    break;
                }
                cost[v0][v1]=c;
                cost[v1][v0]=c;
                System.out.println(v0+" - "+v1+" cost:"+c);
            }
            int v=in.nextInt();
            System.out.println("Source: "+v);
            dijkstra(v);
            int sum=0;
            for (int i = 0; i < V; i++) {
                sum+=d[i];
                System.out.println(v+" - "+i+" cost:"+d[i]);
            }
            System.out.println("Total cost: "+sum);






        }
    }
    //从顶点v开始dijkstra算法
    public static void dijkstra(int v){
        //初始化
        Arrays.fill(d,INF);//先将所有点都离散开来
        Arrays.fill(used,false);
        d[v]=0;//从顶点v出发
        while (true) {
            int v1=-1;
            //从尚未使用过的顶点中选择一个最小的顶点
            for (int i = 0; i < V; i++) {
                if(!used[i]&&(v1==-1||d[i] 
 Input
 
7
0 2 5
0 1 2
1 2 4
2 3 2
1 3 6
1 4 10
4 5 3
3 5 1
4 6 5
5 6 9
0 0 0
3
 
Output
 
Vertex number: 7
0 - 2 cost:5
0 - 1 cost:2
1 - 2 cost:4
2 - 3 cost:2
1 - 3 cost:6
1 - 4 cost:10
4 - 5 cost:3
3 - 5 cost:1
4 - 6 cost:5
5 - 6 cost:9
Done

Source: 3
3 is used
5 is used
2 is used
4 is used
1 is used
0 is used
6 is used
Done
3 - 0 cost:7
3 - 1 cost:6
3 - 2 cost:2
3 - 3 cost:0
3 - 4 cost:4
3 - 5 cost:1
3 - 6 cost:9
Total cost: 29