一、相关概念
单源最短路径
图中某一顶点到其他各顶点的最短路径，可通过经典的Dijkstra算法求解，此算法是基于贪心算法的策略。
注：如果边上带负权值，Dijkstra并不适用。适用于权值非负的有向图或无向图
图中每一对顶点间的最短路径
可通过Floyd-Warshall算法来求解，此算法是基于动态规划的思想
二、题目
题目
1.png
2.png
思路
这个算法是基于贪心策略的（手动求解思路，参考下图）
代码
import java.util.Scanner;
import java.util.Stack;
/**
*
* <p>
* Description:
* </p>
*
* @author 杨丽金
* @date 2018-8-24
* @version 1.0
*/
public class 最短路径算法 {
public static void main(String[] args) {
new 最短路径算法().exe();
}
/*class Node {
// 节点编号
int num;
}*/
// 用邻接矩阵存储图
class MGraph {
// 节点数
int n;
// 边数
int e;
// 节点(节点编号从0开始)
// Node[] nodes;
// 边
int[][] edges;
public MGraph(int n, int e) {
this.n = n;
this.e = e;
// nodes = new Node[n];
edges = new int[n][n];
// 各个边初始化为一个特别大的值
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
edges[i][j] = 0;
} else {
edges[i][j] = Integer.MAX_VALUE;
}
}
}
}
@Override
public String toString() {
return "MGraph [n=" + n + ", e=" + e + ", nodes=";
}
}
private void exe() {
Scanner scan = new Scanner(System.in);
// 节点数
int N = scan.nextInt();
// 边数
int M = scan.nextInt();
MGraph g = new MGraph(N, M);
// 读入各个边
for (int i = 0; i < M; i++) {
int A = scan.nextInt();
int B = scan.nextInt();
int X = scan.nextInt();
g.edges[A][B] = X;
g.edges[B][A] = X;
}
int S = scan.nextInt();
int T = scan.nextInt();
// 输出
System.out.println(g);
for (int i = 0; i < g.n; i++) {
for (int j = 0; j < g.n; j++) {
System.out.print(g.edges[i][j] + "\t");
}
System.out.println();
}
// 得到最短路径长度{有最短路径：返回长度；无：-1}
int r = getMinimumRoad(g, S, T);
System.out.println();
System.out.println(r);
//
System.out.println("最短路径上的节点");
printPath(S,T,path);
}
/**
* 打印从节点S到节点T的最短路径上经过的节点
* @param t
* @param set2
*/
private void printPath(int S,int T, int[] myPath) {
Stack<Integer> stack=new Stack<>();
int i=T;
while(myPath[i]!=-1){
stack.push(i);
i=myPath[i];
}
stack.push(S);
while(!stack.isEmpty()){
// 出栈
int temp=stack.pop();
System.out.print(temp+"\t");
}
System.out.println();
}
/*
* Dijkstra需要3个辅助数组 1,set[] 2,dist[] 3,path[]
*/
// 标志节点是否已找到最短路径
int[] set;
// 标志从起始节点S到节点i的最短路径长度
int[] dist;
// 起始节点S到节点i的最短路径上i的前一节点
int[] path;
/**
* dijkstra算法：基于贪心策略 每次都从dist数组中找出最小的值并入到集合中，然后再更改path、dist集合
*
* @param g
* @param S
* @param T
* @return
*/
private int getMinimumRoad(MGraph g, int S, int T) {
set = new int[g.n];
// 标志从起始节点S到节点i的最短路径长度
dist = new int[g.n];
// 起始节点S到节点i的最短路径上i的前一节点
path = new int[g.n];
/*
* 初始化这些数组 set[] ：初始化时 S节点标志位1，其余的标志位0 dist[]
* :用图的edges[][]数组中的edges[S][i]代替
* path[]:S到i有路径则path[i]=S;若无路径，则path[i]=-1
*/
// set[] ：初始化时 S节点标志位1，其余的标志位0
set[S] = 1;
// dist[] :用图的edges[][]数组中的edges[S][i]代替
for (int i = 0; i < g.n; i++) {
dist[i] = g.edges[S][i];
}
// path[]:S到i有路径则path[i]=S;若无路径，则path[i]=-1
for (int i = 0; i < g.n; i++) {
if (g.edges[S][i] == Integer.MAX_VALUE) {
// 无路径
path[i] = -1;
} else {
path[i] = S;
}
}
path[S] = -1;
System.out.print("set[]:");
for (int i = 0; i < g.n; i++) {
System.out.print(set[i] + "\t");
}
System.out.println();
System.out.print("dist[]:");
for (int i = 0; i < g.n; i++) {
System.out.print(dist[i] + "\t");
}
System.out.println();
System.out.print("path[]:");
for (int i = 0; i < g.n; i++) {
System.out.print(path[i] + "\t");
}
System.out.println();
// 更新set[]、dist[]、path[]
dijkstra(g, set, path, dist);
System.out.print("set[]:");
for (int i = 0; i < g.n; i++) {
System.out.print(set[i] + "\t");
}
System.out.println();
System.out.print("dist[]:");
for (int i = 0; i < g.n; i++) {
System.out.print(dist[i] + "\t");
}
System.out.println();
System.out.print("path[]:");
for (int i = 0; i < g.n; i++) {
System.out.print(path[i] + "\t");
}
return dist[T]==Integer.MAX_VALUE? -1:dist[T];
}
private void dijkstra(MGraph g, int[] set, int[] path, int[] dist) {
// 求最短路径
for (int i = 0; i < g.n - 2; i++) {
// 进行n-2轮循环
// 找出dist[] 中最小的k（太贪心）
int k = -1;
int min = Integer.MAX_VALUE;
for (int j = 0; j < g.n; j++) {
if (set[j] == 0) {
// 还未并入集合
if (dist[j] < min) {
min = dist[j];
k = j;
}
}
}
// 将上述k节点并入集合set中，更新path[]、dist[]
set[k] = 1;
for (int m = 0; m < g.n; m++) {
if (set[m] == 0) {
// 还未合并入集合
// 更新dist// 更新path
if(g.edges[k][m]==Integer.MAX_VALUE){
// k到m无路径，则不用再往下判断了
continue;
}
int temp = dist[k] + g.edges[k][m];
if (temp < dist[m]) {
dist[m] = temp;
path[m] = k;
}
}
}
}
}
}
网友评论