迪杰斯特拉算法模板
2021/11/15 11:10:03
本文主要是介绍迪杰斯特拉算法模板,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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} */
这篇关于迪杰斯特拉算法模板的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)