问题描述
在带权有向图G中，给定一个源点v，求从v到G中的其余各顶点的最短路径问题，叫做单源点的最短路径问题。
在常用的单源点最短路径算法中，迪杰斯特拉算法是最为常用的一种，是一种按照路径长度递增的次序产生最短路径的算法。
在本题中，读入一个无向图的带权邻接矩阵（即数组表示），求出源点至每一个其它顶点的最短路径长度。
输入
输入的第一行包含1个正整数n表示图中共有n个顶点，其中n不超过50。
输入的第二行包含一个大写字母M(M – A < n)
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为10000，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为10000。
输出
共n – 1行
每一行表示源点到其余各点的最短路径长度
解法：贪心思想
Idea
（1）用两个集合S 和 U
S：表示已经求出最短路径的顶点以及相应的最短路径长度
U：表示未求出最短路径的顶点以及该顶点到源点的长度
（2）记录下上一个已经找到的最短路径上的顶点，用pre表示
（3）更新U中的value值，用U中每个顶点到源点的距离 和 与上一个找到的顶点的距离 + 上一个顶点到源点的最短距离，取最小值
（4）找到U中到源点距离最小的那个顶点min
（5）将min添加到S中去，并且将min从U中删除
（6）循环（3）-（5），直到U中没有顶点时结束
（7）S中存储的就是到各个顶点的最短距离
以无向图为例模拟过程
代码
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* 有向图找最短路径
*/
public class Main2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入顶点个数
int n = scanner.nextInt();
// 输入起始顶点
int V0 = scanner.nextInt();
int[][] arr = new int[n][n];
// 输入邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int num = scanner.nextInt();
arr[i][j] = num == 0 ? 10000 : num;
}
}
// 迪杰斯特拉算法，求出到其余顶点的最短距离
Map<Integer, Integer> result = dijkstra(arr, V0);
// 输出结果
for (int i = 0; i < n; i++) {
if(i != V0){
if(result.get(i) == 10000){
System.out.print(-1 + " ");
}else {
System.out.print(result.get(i) + " ");
}
}
}
}
/**
* 迪杰斯特拉算法
* @param arr 邻接矩阵
* @param V0 起始顶点
* @return 返回到各个顶点的单源最短路径长度
*/
private static Map<Integer, Integer> dijkstra(int[][] arr, int V0) {
int n = arr.length;
// 存储已求出最短路径的顶点，以及相应的最短路径长度
Map<Integer, Integer> S = new HashMap<>();
// 存储还未求出最短路径的顶点，以及该顶点到起点的距离
Map<Integer, Integer> U = new HashMap<>();
// 将起点放入S
S.put(V0, 10000);
// 将剩余的点放入U
for (int i = 0; i < n; i++) {
if(i != V0){
U.put(i, getDistence(arr, V0, i));
}
}
// 上一个找到的顶点
int pre = V0;
// 每次循环找到剩余顶点中的最小值
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n; j++) {
if(U.get(j) != null){
// 比较从当前点到起点的距离 和 当前点到上一个找到的点距离+上一个点到起点的距离
int min = Math.min(U.get(j), S.get(pre) + getDistence(arr, pre, j));
U.put(j, min);
}
}
// 从U中删除最小距离，添加到S中
pre = deleteAndAddMin(U, S, n);
}
return S;
}
/**
* 将U中距离起点最短的顶点增加到S中，并从U中删除
* @param u
* @param s
* @return 顶点编号
*/
private static Integer deleteAndAddMin(Map<Integer, Integer> u, Map<Integer, Integer> s, int n) {
int minIndex = 0;
// 找到第一个不为空的下标
while (u.get(minIndex) == null){
minIndex ++;
}
int min = u.get(minIndex);
// 找到U中的最短那个距离
for (int i = 0; i < n; i++) {
if(u.get(i) != null){
if(u.get(minIndex) > u.get(i)){
minIndex = i;
min = u.get(i);
}
}
}
// 将最短那个距离添加到S中，并从U中删除
s.put(minIndex, min);
u.remove(minIndex);
return minIndex;
}
/**
* 获取两个顶点的距离
* @param arr
* @param v0
* @param i
* @return
*/
private static Integer getDistence(int[][] arr, int v0, int i) {
return arr[v0][i];
}
}提交结果
下面给出无向图的解法：
import java.util.*;
/**
* 单源最短路径问题
* 如果两个点之间不连通，则设置边的值为10000
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入顶点个数
int n = scanner.nextInt();
// 吸收换行符
String s = scanner.nextLine();
// 输入起始顶点
int V0 = (int)(scanner.nextLine().charAt(0) - 'A');
int[][] arr = new int[n][n];
// 输入邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = scanner.nextInt();
}
}
// 迪杰斯特拉算法，求出到其余顶点的最短距离
Map<Integer, Integer> result = dijkstra(arr, V0);
// 输出结果
for (int i = 0; i < n; i++) {
if(i != V0){
System.out.println("从 " + (char)(V0 + 'A') + " 顶点到 " + (char)(i + 'A') + " 顶点的最短距离为：" + result.get(i));
}
}
}
/**
* 迪杰斯特拉算法
* @param arr 邻接矩阵
* @param V0 起始顶点
* @return 返回到各个顶点的单源最短路径长度
*/
private static Map<Integer, Integer> dijkstra(int[][] arr, int V0) {
int n = arr.length;
// 存储已求出最短路径的顶点，以及相应的最短路径长度
Map<Integer, Integer> S = new HashMap<>();
// 存储还未求出最短路径的顶点，以及该顶点到起点的距离
Map<Integer, Integer> U = new HashMap<>();
// 将起点放入S
S.put(V0, 10000);
// 将剩余的点放入U
for (int i = 0; i < n; i++) {
if(i != V0){
U.put(i, getDistence(arr, V0, i));
}
}
// 上一个找到的顶点
int pre = V0;
// 每次循环找到剩余顶点中的最小值
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n; j++) {
if(U.get(j) != null){
// 比较从当前点到起点的距离 和 当前点到上一个找到的点距离+上一个点到起点的距离
int min = Math.min(U.get(j), S.get(pre) + getDistence(arr, pre, j));
U.put(j, min);
}
}
// 从U中删除最小距离，添加到S中
pre = deleteAndAddMin(U, S, n);
}
return S;
}
/**
* 将U中距离起点最短的顶点增加到S中，并从U中删除
* @param u
* @param s
* @return 顶点编号
*/
private static Integer deleteAndAddMin(Map<Integer, Integer> u, Map<Integer, Integer> s, int n) {
int minIndex = 0;
// 找到第一个不为空的下标
while (u.get(minIndex) == null){
minIndex ++;
}
int min = u.get(minIndex);
// 找到U中的最短那个距离
for (int i = 0; i < n; i++) {
if(u.get(i) != null){
if(u.get(minIndex) > u.get(i)){
minIndex = i;
min = u.get(i);
}
}
}
// 将最短那个距离添加到S中，并从U中删除
s.put(minIndex, min);
u.remove(minIndex);
return minIndex;
}
/* 获取两个顶点的距离 */
private static Integer getDistence(int[][] arr, int v0, int i) {
return arr[v0][i];
}
}运行结果
作者：喻航
本文标题：求最短路径（迪杰特斯拉算法）
本文链接：https://onedawn.cn/greed/156.html
版权声明：如无特别声明，本文即为原创文章，仅代表个人观点，版权归 雾满拦江 所有，未经允许不得转载！
