当前位置 博文首页 > kbtx的博客:【王道408】迪杰斯特拉和弗洛伊德算法的演示
初始化时用到的图如下
import java.util.Arrays;
public class Graph {
int[][] table;int size;
boolean[] fin;int[] distance,path;
static final int UNACCESSIBLE = -1;
//值设置过大会溢出
static final int inf = Integer.MAX_VALUE/16;
Graph(int[][] t){
if(t.length!=t[0].length) {System.err.println("邻接表空间分配错误");return;}
table = t;
size = t.length;
//将不可达替换成最大值表示,防止负权值问题影响计算
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
if(table[i][j]==UNACCESSIBLE) table[i][j] = inf;
}
}
}
/**
* 找到一个尚未确定最短路径的,离v最近的顶点
* @return 顶点号
*/
private int Dijkstra_nearest(){
int min_v = inf;
int pos = -1;
for(int i=0;i<size;i++){
if(!fin[i]&&distance[i]<min_v){
min_v = distance[i];
pos = i;
}
}
if(0<=pos) fin[pos] = true;
return pos;
}
/**
* 判定是否为所有节点找到最短路径
* @return 判断结果
*/
private boolean Dijkstra_finish(){
for(int i=0;i<size;i++){
if(!fin[i]) return false;
}
return true;
}
/**
* 构建一条更短的路径
* pos 中介节点
* v 源节点
*/
private void Dijkstra_build_path(int pos,int v){
for(int i=0;i<size;i++){
//直达的距离
int direct_dis = table[v][i];
//通过中介到达的距离
int proxy_dis = distance[pos] + table[pos][i];
//对于一个尚未确定最短距离的节点(为了防止溢出现象混淆视听),如果通过中介到达目的的距离比直达短
if(!fin[i] && proxy_dis<direct_dis){
//将最短路径修改为通过中介到达的值
distance[i] = proxy_dis;
//将中介节点记录在path上
path[i] = pos;
}
}
}
/**
* 计算给定顶点到其他边的最短路径
* @param v 顶点号
* @return 最短路径数组,每一个值代表从v到当前节点的最短路径的前驱
*/
public int[] Dijkstra(int v){
//每个顶点的最短路径直接前驱
path = new int[size];
//求得的最短距离
distance = new int[size];
//是否找到最短路径
fin = new boolean[size];
//以下是初始化代码
for(int i=0;i<size;i++){
path[i] = v;
distance[i] = table[v][i];
fin[i] = false;
}
//找到家门口了
path[v] = -1;
distance[v] = 0;
fin[v] = true;
//下面进入循环更新信息
while(!Dijkstra_finish()){
//首先找到一个尚未确定最短路径的,离v最近的顶点,可以获取到这个顶点的位置
int pos = Dijkstra_nearest();
//接下来构建路径
Dijkstra_build_path(pos,v);
}
return path;
}
public int[][] Floyd(){
int[][] path = new int[size][size];
int[][] dis_table = table.clone();
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
path[i][j] = UNACCESSIBLE;
}
}
//逐一选取中转节点
for(int proxy=0;proxy<size;proxy++){
for(int from=0;from<size;from++){
for(int to=0;to<size;to++){
//目前距离表中的距离大小
int current_dis = dis_table[from][to];
//允许从新的中介节点中转后的距离大小
int dis_allow_new_proxy = dis_table[from][proxy] + dis_table[proxy][to];
//如果通过中介可以缩短距离
if(dis_allow_new_proxy < current_dis){
System.out.printf("将从%d到%d的路径由%d缩短到%d,经过节点%d\n",from,to,current_dis,dis_allow_new_proxy,proxy);
//记录最短距离
dis_table[from][to] = dis_allow_new_proxy;
//就将这个中介标记在路径表上
path[from][to] = proxy;
}
//上面的算法无法记录不需要经过中介的节点的路径,因此额外添加判断以起补充作用,如果dis_allow_new_proxy==inf,说明中介节点与源或目的节点重合
if(dis_allow_new_proxy!=inf && dis_allow_new_proxy==current_dis && path[from][to]==UNACCESSIBLE){
System.out.printf("将从%d到%d的路径由%d缩短到%d,经过节点%d\n",from,to,current_dis,dis_allow_new_proxy,proxy);
//就将这个中介标记在路径表上
path[from][to] = proxy;
}
}
}
}
return path;
}
public static void main(String[] args) {
int[][] t = {
{0,10,-1,-1,5},
{-1,0,1,-1,2},
{-1,-1,0,4,-1},
{7,-1,6,0,-1},
{-1,3,9,2,0}};
Graph g = new Graph(t);
System.out.println(Arrays.toString(g.Dijkstra