一、核心思想
和Prime算法的思想几乎相同,Prime算法中是使用lowcost数组保存到生成树之间的最短距离,Dijkstra算法中使用lowcost数组保存到第一个节点的最短路径。
二、和Prime算法的不同之处
Dijkstra算法和Prime算法相似度达到了99%,和Prime算法相比,Dijkstra算法有以下几点不同之处:
1. 最大的不同之处是lowcost数组的刷新方式不同,Prime算法的刷新方式:
for(int j=1;j<=nodeCount;j++){ if(lowcost[j]!=-1&&lowcost[j]>map[k][j]){ lowcost[j]=map[k][j]; } }
Dijkstra算法的刷新方式:
for(int j=1;j<=nodeCount;j++){ if(visited[j]==false&&lowcost[j]>(map[j][k]+minEdge)){ lowcost[j]=map[j][k]+minEdge; } }
2.使用Prime算法可以使用lowcost数组作为标志数组,可以使用lowcost[i]=-1来标识当前节点已经加入生成树,但是在Dijkstra算法中该lowcost数组保存着到节点一的最短路径值,所以必须重新定义一个标识数组visited来标识一个节点是否已经被访问过(可以在Prime算法中使用该数组,那么Dijkstra算法和Prime算法只有1中的不同之处了)
3.由于刷新lowcost数组的方式发生了改变,导致作为“无限大”标识的maxIntegerValue不能再使用(1<<31)-1,可以使用(1<<15)-1作为标志性的”无限大“
三、代码实现(Java版)
import java.util.Scanner; public class Dijkstra { private static final int maxIntegerValue=(1<<15)-1; public static void main(String args[]){ Scanner scanner=new Scanner(System.in); int[][] map=new int[101][101]; boolean[] visited=new boolean[101]; while(scanner.hasNext()){ init(map,visited); int nodeCount=scanner.nextInt(); int edgeCount=scanner.nextInt(); for(int i=0;i<edgeCount;i++){ int node1=scanner.nextInt(); int node2=scanner.nextInt(); int edgeValue=scanner.nextInt(); if(map[node1][node2]>edgeValue){ map[node1][node2]=edgeValue; map[node2][node1]=edgeValue; } } int shortestPathCost=dijkstra(nodeCount,map,visited); System.out.println(shortestPathCost); } } public static int dijkstra(int nodeCount,int[][] map,boolean[] visited){ int lowcost[]=new int[101]; lowcost[1]=0; visited[1]=true; for(int i=2;i<=nodeCount;i++){ lowcost[i]=map[1][i]; } for(int i=1;i<=nodeCount-1;i++){ int minEdge=maxIntegerValue; int k=0; for(int j=1;j<=nodeCount;j++){ if(visited[j]==false&&lowcost[j]<minEdge){ k=j; minEdge=lowcost[j]; } } visited[k]=true; for(int j=1;j<=nodeCount;j++){ if(visited[j]==false&&lowcost[j]>(map[j][k]+minEdge)){ lowcost[j]=map[j][k]+minEdge; } } } return lowcost[nodeCount]; } public static void init(int[][] map,boolean[] visited){ for(int i=0;i<map.length;i++){ for(int j=0;j<map[i].length;j++){ map[i][j]=maxIntegerValue; } } for(int i=0;i<visited.length;i++){ visited[i]=false; } } }
四、测试数据
输入 6 10 1 2 6 2 5 3 5 6 6 6 4 2 4 1 5 3 1 1 3 2 5 3 5 6 3 6 4 3 4 5 输出 5
五、ACM
题目链接:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2143
AC代码:
import java.util.Scanner; public class Main { private static final int maxIntegerValue=(1<<15)-1; public static void main(String args[]){ Scanner scanner=new Scanner(System.in); int[][] map=new int[101][101]; boolean[] visited=new boolean[101]; while(scanner.hasNext()){ init(map,visited); int nodeCount=scanner.nextInt(); int edgeCount=scanner.nextInt(); for(int i=0;i<edgeCount;i++){ int node1=scanner.nextInt(); int node2=scanner.nextInt(); int edgeValue=scanner.nextInt(); if(map[node1][node2]>edgeValue){ map[node1][node2]=edgeValue; map[node2][node1]=edgeValue; } } int shortestPathCost=dijkstra(nodeCount,map,visited); System.out.println(shortestPathCost); } } public static int dijkstra(int nodeCount,int[][] map,boolean[] visited){ int lowcost[]=new int[101]; lowcost[1]=0; visited[1]=true; for(int i=2;i<=nodeCount;i++){ lowcost[i]=map[1][i]; } for(int i=1;i<=nodeCount-1;i++){ int minEdge=maxIntegerValue; int k=0; for(int j=1;j<=nodeCount;j++){ if(visited[j]==false&&lowcost[j]<minEdge){ k=j; minEdge=lowcost[j]; } } visited[k]=true; for(int j=1;j<=nodeCount;j++){ if(visited[j]==false&&lowcost[j]>(map[j][k]+minEdge)){ lowcost[j]=map[j][k]+minEdge; } } } return lowcost[nodeCount]; } public static void init(int[][] map,boolean[] visited){ for(int i=0;i<map.length;i++){ for(int j=0;j<map[i].length;j++){ map[i][j]=maxIntegerValue; } } for(int i=0;i<visited.length;i++){ visited[i]=false; } } } /* */ /************************************** Problem id : SDUT OJ 2143 User name : kdyzm Result : Accepted Take Memory : 90280K Take Time : 590MS Submit Time : 2016-01-24 13:49:42 **************************************/
相关推荐
总结起来,Dijkstra算法是解决最短路径问题的重要工具,其MATLAB实现使得算法的理解和应用变得更加便捷。通过理解算法原理并掌握MATLAB实现,我们可以更好地利用这一算法解决实际问题,特别是在图论和网络科学领域。
**图的最短路径Dijkstra算法** 在计算机科学和图论中,Dijkstra算法是一种用于寻找图中两个节点间最短路径的经典算法。由荷兰计算机科学家艾兹格·迪科斯彻于1956年提出,这个算法广泛应用于网络路由、地理信息系统...
在这个专题中,我们将聚焦于两个经典图论中的最短路径算法:Dijkstra算法和Floyd-Warshall算法。 Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻提出的,主要用于解决单源最短路径问题。它是一种贪心算法,其...
`Dijkstra_test`文件可能是Dijkstra算法的测试用例,它可能包含了各种图结构和测试数据,用于验证算法的正确性。通常,测试会包括不同的输入,如单源最短路径、多源最短路径、包含环的图、具有大量节点和边的图等,...
Dijkstra算法是图论中的一个重要算法,用于寻找图中一个起点到其他所有点的最短路径。这个算法是由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出的,广泛应用于网络路由、地图导航等领域。在这个问题中,我们需要...
Dijkstra最短路径算法是一种经典的图论算法,用于寻找图中节点间的最短路径。在计算机科学和网络路由中有着广泛的应用。Matlab作为一种强大的数值计算和可视化工具,非常适合用来实现这种算法。在这个项目中,我们有...
数据结构与最短路径算法是计算机科学中的核心概念,尤其在图论和算法设计中占有重要地位。在解决网络中的路径问题,如交通路线、通信网络优化或是游戏中的寻路算法时,最短路径算法起着关键作用。本文将深入探讨最短...
最短路径Dijkstra算法是图论中的一个著名算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。该算法主要用于解决单源最短路径问题,即从图中的一点(源点)出发,寻找到达其他所有顶点的最短路径。在VC++6.0...
在提供的项目"最短路径Dijkstra算法成品"中,开发者已经实现了这些概念。你可以通过查看源代码来理解每个部分是如何工作的,包括图的表示、优先队列的管理、Dijkstra算法的实现以及可能的测试用例。这将帮助你深入...
传统的解决最短路径问题的方法包括Dijkstra算法、Floyd算法等。其中,Dijkstra算法是一种经典的算法,适用于没有负权边的有向图或无向图中,能够有效地计算出单源点到其他所有节点的最短路径。 然而,随着应用规模...
数据结构与算法是计算机科学的基础,其中Dijkstra算法是一种经典的最短路径算法,它由荷兰计算机科学家艾兹格·迪科斯彻于1956年提出,主要用于解决图论中的单源最短路径问题。在这个场景中,我们讨论的是在一个包含...
综上所述,图论中的最短路径问题及其算法在实际应用中具有广泛价值,Dijkstra算法是解决此类问题的有效工具。通过编程实现,我们可以创建出能够解决各种实际问题的软件工具,这些工具不仅能够帮助决策者找到最优解,...
这份"C语言算法与数据结构最短路径报告+代码"压缩包,显然是为了帮助初学者理解和应用这些概念。以下是对其中涉及的主要知识点的详细阐述: 1. **C语言**:C语言是一种强大的、低级的编程语言,广泛用于系统编程、...
Dijkstra算法是解决单源最短路径问题的一种高效算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。本篇文章将详细探讨Dijkstra串行算法的实现及其在C++中的应用。 Dijkstra算法的基本思想是从源节点出发,...
Dijkstra算法是图论中的一个经典算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出,主要用于寻找有向图或无向图中源节点到其他所有节点的最短路径。在这个Java实现中,我们专注于解决两城市间的最短路径问题。...
Dijkstra算法,由荷兰计算机科学家艾兹格·迪科斯彻于1956年提出,是一种用于寻找图中两点间最短路径的算法。在图论和计算机科学中,这个算法广泛应用于网络路由、地图导航、任务调度等多个领域。在MATLAB中实现...
总结来说,Dijkstra算法是一种用于求解单源最短路径问题的有效方法,它通过贪心策略逐步扩展最短路径,适用于无负权边的图。在实际编程实现中,需要考虑优化数据结构以提高效率,如使用优先队列。理解并熟练运用...
本话题将深入探讨数据结构中的最短路径算法及其C++实现。最短路径问题广泛应用于网络路由、物流配送、社交网络分析等多个领域,解决的是如何在图中找到从一个顶点到另一个顶点的最短路径。 一、Dijkstra算法 ...
最短路径算法是图论中的一个核心问题,用于寻找网络中的两点之间路径成本最低的路径。在计算机科学和信息技术领域,这种算法有着广泛的应用,如路由选择、物流规划、社交网络分析等。C#作为一门面向对象的编程语言,...
数据结构中的最短路径算法是计算机科学中一个关键的研究领域,尤其在图论与网络流问题中占有重要的地位。在给定的标题“数据结构最短路径算法实现”和描述中,我们可以理解到该主题主要关注如何在不同类型的图(有向...