`
狂盗一枝梅
  • 浏览: 18171 次
  • 性别: Icon_minigender_1
  • 来自: 青岛
社区版块
存档分类
最新评论

【数据结构】【图论】【最短路径】Dijkstra算法

阅读更多

一、核心思想

       和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实现_dijkstra_最短路径算法_

    总结起来,Dijkstra算法是解决最短路径问题的重要工具,其MATLAB实现使得算法的理解和应用变得更加便捷。通过理解算法原理并掌握MATLAB实现,我们可以更好地利用这一算法解决实际问题,特别是在图论和网络科学领域。

    图的最短路径dijkstra算法

    **图的最短路径Dijkstra算法** 在计算机科学和图论中,Dijkstra算法是一种用于寻找图中两个节点间最短路径的经典算法。由荷兰计算机科学家艾兹格·迪科斯彻于1956年提出,这个算法广泛应用于网络路由、地理信息系统...

    数据结构 c++ 最短路径Dijkstra和Floyd

    在这个专题中,我们将聚焦于两个经典图论中的最短路径算法:Dijkstra算法和Floyd-Warshall算法。 Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻提出的,主要用于解决单源最短路径问题。它是一种贪心算法,其...

    最短路径算法Dijkstra源代码

    `Dijkstra_test`文件可能是Dijkstra算法的测试用例,它可能包含了各种图结构和测试数据,用于验证算法的正确性。通常,测试会包括不同的输入,如单源最短路径、多源最短路径、包含环的图、具有大量节点和边的图等,...

    求最短路径Dijkstra算法

    Dijkstra算法是图论中的一个重要算法,用于寻找图中一个起点到其他所有点的最短路径。这个算法是由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出的,广泛应用于网络路由、地图导航等领域。在这个问题中,我们需要...

    Dijkstra最短路径算法的Matlab实现

    Dijkstra最短路径算法是一种经典的图论算法,用于寻找图中节点间的最短路径。在计算机科学和网络路由中有着广泛的应用。Matlab作为一种强大的数值计算和可视化工具,非常适合用来实现这种算法。在这个项目中,我们有...

    数据结构。最短路径算法

    数据结构与最短路径算法是计算机科学中的核心概念,尤其在图论和算法设计中占有重要地位。在解决网络中的路径问题,如交通路线、通信网络优化或是游戏中的寻路算法时,最短路径算法起着关键作用。本文将深入探讨最短...

    最短路径Dijkstra算法

    最短路径Dijkstra算法是图论中的一个著名算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。该算法主要用于解决单源最短路径问题,即从图中的一点(源点)出发,寻找到达其他所有顶点的最短路径。在VC++6.0...

    C#实现最短路径Dijkstra算法

    在提供的项目"最短路径Dijkstra算法成品"中,开发者已经实现了这些概念。你可以通过查看源代码来理解每个部分是如何工作的,包括图的表示、优先队列的管理、Dijkstra算法的实现以及可能的测试用例。这将帮助你深入...

    基于数据结构的最短路径算法的研究.pdf

    传统的解决最短路径问题的方法包括Dijkstra算法、Floyd算法等。其中,Dijkstra算法是一种经典的算法,适用于没有负权边的有向图或无向图中,能够有效地计算出单源点到其他所有节点的最短路径。 然而,随着应用规模...

    数据结构-最短路径

    数据结构与算法是计算机科学的基础,其中Dijkstra算法是一种经典的最短路径算法,它由荷兰计算机科学家艾兹格·迪科斯彻于1956年提出,主要用于解决图论中的单源最短路径问题。在这个场景中,我们讨论的是在一个包含...

    图论中最短路径问题算法程序的开发1

    综上所述,图论中的最短路径问题及其算法在实际应用中具有广泛价值,Dijkstra算法是解决此类问题的有效工具。通过编程实现,我们可以创建出能够解决各种实际问题的软件工具,这些工具不仅能够帮助决策者找到最优解,...

    c语言算法与数据结构最短路径报告+代码.zip

    这份"C语言算法与数据结构最短路径报告+代码"压缩包,显然是为了帮助初学者理解和应用这些概念。以下是对其中涉及的主要知识点的详细阐述: 1. **C语言**:C语言是一种强大的、低级的编程语言,广泛用于系统编程、...

    最短路径Dijkstra串行算法

    Dijkstra算法是解决单源最短路径问题的一种高效算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。本篇文章将详细探讨Dijkstra串行算法的实现及其在C++中的应用。 Dijkstra算法的基本思想是从源节点出发,...

    两个城市的最短路径dijkstra算法Java代码

    Dijkstra算法是图论中的一个经典算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出,主要用于寻找有向图或无向图中源节点到其他所有节点的最短路径。在这个Java实现中,我们专注于解决两城市间的最短路径问题。...

    Dijkstra算法找最短路径代码,dijkstra算法求最短路径,matlab

    Dijkstra算法,由荷兰计算机科学家艾兹格·迪科斯彻于1956年提出,是一种用于寻找图中两点间最短路径的算法。在图论和计算机科学中,这个算法广泛应用于网络路由、地图导航、任务调度等多个领域。在MATLAB中实现...

    最短路径的 dijkstra算法

    总结来说,Dijkstra算法是一种用于求解单源最短路径问题的有效方法,它通过贪心策略逐步扩展最短路径,适用于无负权边的图。在实际编程实现中,需要考虑优化数据结构以提高效率,如使用优先队列。理解并熟练运用...

    数据结构-最短路径算法实现

    本话题将深入探讨数据结构中的最短路径算法及其C++实现。最短路径问题广泛应用于网络路由、物流配送、社交网络分析等多个领域,解决的是如何在图中找到从一个顶点到另一个顶点的最短路径。 一、Dijkstra算法 ...

    最短路径算法c# 最短路径算法

    最短路径算法是图论中的一个核心问题,用于寻找网络中的两点之间路径成本最低的路径。在计算机科学和信息技术领域,这种算法有着广泛的应用,如路由选择、物流规划、社交网络分析等。C#作为一门面向对象的编程语言,...

    数据结构最短路径算法实现

    数据结构中的最短路径算法是计算机科学中一个关键的研究领域,尤其在图论与网络流问题中占有重要的地位。在给定的标题“数据结构最短路径算法实现”和描述中,我们可以理解到该主题主要关注如何在不同类型的图(有向...

Global site tag (gtag.js) - Google Analytics