贪心算法-单源最短路径
算法思想：贪心算法
实际问题：单源最短路径
编程语言：Java
问题描述
单源最短路径算法，又称 迪杰斯特拉算法 。其目的是寻找从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。
算法构造
相关解释
- 观测域：假设起点为v点，观测域便为v点的四周，即v的所有邻接点；
- 点集 V：图中所有点的集合；
- 点集 S：已经找到最短路径的终点集合；
- 数组 D：存储观测域内能观测到的最短路径，算上起点一共 n 个数值。比如 D[k] 对应在观测域中能观测到的，到顶点 k 的最短路径；
- 邻接矩阵 a：存储着有权图中的边的信息，是一个二维数组。比如 a[1][2] = 5 表示在有权图中，点 1 和点 2 之间有边，且边的权值为 5。如果两点之间没边，则用负数或则无穷大(∞)表示。
算法步骤
- 第一步：初始化点集 S，将起点 v 收入 S 中。初始化数组 D：D[k] = a[v][k]；
- 第二步：找寻次短路径。即查找数组 D，找出观测域中最短路径(v, j)：D[j] = min(D[k] | k 不属于 S)。将点 j 加入点集 S 中；
- 第三步：将 j 的邻接点并入观测域，即用 j 的邻接点更新数组 D；
- 第四步：不断重复第二步和第三步，直到节点全部压入 S 中为止。
注：贪心算法的思想主要就体现在第二步和第三步之中。
Java 代码
本代码求解的是无向有权图的最短路径，如果想求有向有权图的最短路径，则只需要将无向图的邻接矩阵改为有向图的邻接矩阵即可。
import java.util.Scanner;
public class SSSP
{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
System.out.print("请输入图的顶点和边的个数(格式：顶点个数 边个数)：");
int n = input.nextInt(); //顶点的个数
int m = input.nextInt(); //边的个数
System.out.println();
int[][] a = new int[n + 1][n + 1];
//初始化邻接矩阵
for(int i = 0; i < a.length; i++)
{
for(int j = 0; j < a.length; j++)
{
a[i][j] = -1; //初始化没有边
}
}
System.out.println("请输入图的路径长度(格式：起点 终点 长度)：");
//总共m条边
for(int i = 0; i < m; i++)
{
//起点，范围1到n
int s = input.nextInt();
//终点，范围1到n
int e = input.nextInt();
//长度
int l = input.nextInt();
if(s >= 1 && s <= n && e >= 1 && e <= n)
{
//无向有权图
a[s][e] = l;
a[e][s] = l;
}
}
System.out.println();
//距离数组
int[] dist = new int[n+1];
//前驱节点数组
int[] prev = new int[n+1];
int v =1 ;//顶点，从1开始
dijkstra(v, a, dist, prev);
}
/**
* 单源最短路径算法(迪杰斯特拉算法)
* @param v 顶点
* @param a 邻接矩阵表示图
* @param dist 从顶点v到每个点的距离
* @param prev 前驱节点数组
*/
public static void dijkstra(int v, int[][] a, int[] dist, int[] prev)
{
int n = dist.length;
/**
* 顶点从1开始，到n结束，一共n个结点
*/
if(v > 0 && v <= n)
{
//顶点是否放入的标志
boolean[] s = new boolean[n];
//初始化
for(int i = 1; i < n; i++)
{
//初始化为 v 到 i 的距离
dist[i] = a[v][i];
//初始化顶点未放入
s[i] = false;
//v到i无路，i的前驱节点置空
if(dist[i] == -1)
{
prev[i] = 0;
}
else
{
prev[i] = v;
}
}
//v到v的距离是0
dist[v] = 0;
//顶点放入
s[v] = true;
//共扫描n-2次，v到v自己不用扫
for(int i = 1; i < n - 1; i++)
{
int temp = Integer.MAX_VALUE;
//u为下一个被放入的节点
int u = v;
//这个for循环为第二步，观测域为v的观测域
//遍历所有顶点找到下一个距离最短的点
for(int j = 1; j < n; j++)
{
//j未放入，且v到j有路，且v到当前节点路径更小
if(!s[j] && dist[j] != -1 && dist[j] < temp)
{
u = j;
//temp始终为最小的路径长度
temp = dist[j];
}
}
//将得到的下一节点放入
s[u] = true;
//这个for循环为第三步，用u更新观测域
for(int k = 1; k < n; k++)
{
if(!s[k] && a[u][k] != -1)
{
int newdist=dist[u] + a[u][k];
if(newdist < dist[k] || dist[k] == -1)
{
dist[k] = newdist;
prev[k] = u;
}
}
}
}
}
for(int i = 2; i < n; i++)
{
System.out.println(i + "节点的最短距离是："
+ dist[i] + "；前驱点是：" + prev[i]);
}
}
}
运行结果
