无向图最短路径问题

news/2024/7/3 5:52:30

题目：无向图G有N个结点(1<N<=1000)及一些边，每一条边上带有正的权重值。找到结点1到结点N的最短路径，或者输出不存在这样的路径。

解决思路：动态规划

1、首先使用邻接矩阵存储无向图

2、将找到结点1到节点N的最短路径分解成结点1到节点i的最短路径（1<i<节点数）

3、对于每一个未计算的结点i，考虑已经计算过的当前最短路径端点choice,如果结点i和结点j直接有边，则计算从结点choice到未计算结点的最短路径

d[i]=min{A[i][j]+A[j]}

源码

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.lang.Integer;
import java.util.Set;

public class NoPointerChart {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();   //输入点数
        int E = in.nextInt();   //输入边数

        int[][] A = new int[V][V];

        for (int i = 0; i < V; i++) {   //初始化所有边为无穷大
            for (int j = 0; j < V; j++) {
                A[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < E; i++) {   //输入每一条边
            int j = in.nextInt();
            int k = in.nextInt();
            int v = in.nextInt();
            A[j - 1][k - 1] = v;
            A[k - 1][j - 1] = v;
        }

        Set<Integer> unVisited = new HashSet<>(V);  //记录未访问节点
        Set<Integer> visitied = new HashSet<>(V); //记录已经访问的节点
        int[] d = new int[V];
        for (int i = 1; i < V; i++) {   //初始化最优解都为无限大
            unVisited.add(i);
            d[i] = Integer.MAX_VALUE;
        }
        visitied.add(0);
        d[0] = 0;

        int choice = 0;  //中间节点下标，每次选出当前结点到所有可达未标记结点的最短路径端点
        while (unVisited.size() > 0) {   //当仍然有未标记结点的时候 
            int tempMin = Integer.MAX_VALUE;  //记录从中间节点到所有可达结点中的最小值（最短路径）
            int tempMinI = -1;  //记录最短路径的端点下标
            Iterator<Integer> iti = unVisited.iterator();
            while (iti.hasNext()) {  //对于所有未标记的结点
                int i = iti.next();
                if (A[choice][i] != Integer.MAX_VALUE) {   //如果中间结点到此未标记结点有边
                    if(d[i]>A[choice][i] + d[choice])   //计算中间结点到当前结点的最短路径
                        d[i] = A[choice][i] + d[choice];
                    if (d[i] < tempMin) {   //计算当前结点到所有可达未标记结点的最短路径
                        tempMin = d[i]; 
                        tempMinI = i;
                    }

                }
            }
            unVisited.remove(tempMinI);visitied.add(tempMinI);  //将当前结点记录未已经标记
            choice = tempMinI; //重新定位中间结点
        }

        System.out.println(d[V-1]);
    }
//测试用例 第一行输入结点数V和边数E ，以下E行输入每条边的端点和权值
//6 9
//1 2 6
//1 3 3
//2 3 2
//2 4 5
//3 4 3
//3 5 4
//4 5 2
//4 6 3
//5 6 5
}

复制代码