本文主要是介绍迪杰斯特拉算法模板,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
class Djstl {
int[] dist; //到i点的最短路
Boolean[] visited; //点是否被访问。
int l; //邻接矩阵中的点的个数。
public Djstl(int[][] v) { //构造方法初始化,v表示邻接矩阵。
l = v.length;
dist = new int[l];
visited = new Boolean[l];
for (int i = 0; i < l; i++) {
visited[i] = false;
}
}
public void djstl(int s, int[][] v) { //s表示起点。
visited[s] = true; //标记起点已被访问。
dist[s] = 0; //起点的距离为0
int u = 0;
int i, j, k;
for (i = 0; i < l; i++) {
//dist初始化,把起点到各点的距离赋值给dist
dist[i] = v[s][i];
}
for (k = 0; k < l - 1; k++) {
int min = Integer.MAX_VALUE;
//寻找没有被标记且最小的权值点。
for (j = 0; j < l; j++) {
if (!visited[j] && min > dist[j]) {
min = dist[j];
u = j;
}
}
visited[u] = true;
//更新dist数组,如果A到B的距离大于A从C到B的距离,则更新A到B的最短距离
for (i = 0; i < l; i++) {
if (!visited[i] && dist[i] > dist[u] + v[u][i]) {
dist[i] = dist[u] + v[u][i];
}
}
}
}
public static void main(String[] args) {
int max = 9999;
int[][] v = new int[][]{{0, 6, 8, max, max,max}, {6, 0, max, 12, 14, max}, {8, max, 0, 16, 17, max},
{max, 12, 16, 0, max, 15}, {max, 14, 17, max, 0, 5}, {max, max, max, 15, 5, 0}};
Djstl dl = new Djstl(v);
dl.djstl(0, v);
for (int j = 0; j < v.length; j++) {
for (int k = 0; k < v[0].length; k++) {
System.out.print(" " + v[j][k]);
}
System.out.println(" ");
}
System.out.println(" ");
for (int i = 0; i < v.length; i++) {
System.out.print(" " + dl.dist[i]);
}
}
}
/*
无向图
{0, 6, 8, max, max, max}, {6, 0, max, 12, 14, max}, {8, max, 0, 16, 17, max},
{max, 12, 16, 0, max, 15}, {max, 14, 17, max, 0, 5}, {max, max, max, 15, 5, 0}
有向图:
{0,20,15,max,max},{max,0,35,10,max},{max,max,0,30,10},{max,max,max,0,max},{max,max,max,max,0}
*/
这篇关于迪杰斯特拉算法模板的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!