`
128kj
  • 浏览: 604228 次
  • 来自: ...
社区版块
存档分类
最新评论

单源最短路径( Dijkstra算法)JAVA实现

    博客分类:
阅读更多
      单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。

一.最短路径的最优子结构性质

   该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

   假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P'(k,s),那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

二.Dijkstra算法

  Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止。

public class Dijkstra {
    static int M=10000;(此路不通)
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[][] weight1 = {//邻接矩阵
                {0,3,2000,7,M},
                {3,0,4,2,M},
                {M,4,0,5,4},
                {7,2,5,0,6},    
                {M,M,4,6,0}
        };


        int[][] weight2 = {
                {0,10,M,30,100},
                {M,0,50,M,M},
                {M,M,0,M,10},
                {M,M,20,0,60},
                {M,M,M,M,0}
        };
        int start=0;
        int[] shortPath = Dijsktra(weight2,start);
        
        for(int i = 0;i < shortPath.length;i++)
             System.out.println("从"+start+"出发到"+i+"的最短距离为:"+shortPath[i]);  
          
    }
    

    public static int[] Dijsktra(int[][] weight,int start){
     //接受一个有向图的权重矩阵,和一个起点编号start(从0编号,顶点存在数组中)
        //返回一个int[] 数组,表示从start到它的最短路径长度
        int n = weight.length;        //顶点个数
        int[] shortPath = new int[n];    //存放从start到其他各点的最短路径
        String[] path=new String[n]; //存放从start到其他各点的最短路径的字符串表示
         for(int i=0;i<n;i++)
             path[i]=new String(start+"-->"+i);
        int[] visited = new int[n];   //标记当前该顶点的最短路径是否已经求出,1表示已求出
        
        //初始化,第一个顶点求出
        shortPath[start] = 0;
        visited[start] = 1;

        for(int count = 1;count <= n - 1;count++)  //要加入n-1个顶点
        {
 
            int k = -1;    //选出一个距离初始顶点start最近的未标记顶点
            int dmin = Integer.MAX_VALUE;
            for(int i = 0;i < n;i++)
            {
                if(visited[i] == 0 && weight[start][i] < dmin)
                {
                    dmin = weight[start][i];
                   
                    k = i;
                }  
                    
            }
           // System.out.println("k="+k);
             
            //将新选出的顶点标记为已求出最短路径,且到start的最短路径就是dmin
            shortPath[k] = dmin;

            visited[k] = 1;
  
            //以k为中间点,修正从start到未访问各点的距离
            for(int i = 0;i < n;i++)
            {                 
                if(visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]){
                     weight[start][i] = weight[start][k] + weight[k][i];
                   
                     path[i]=path[k]+"-->"+i;
                 
                }
                
            }  
     
        }
         for(int i=0;i<n;i++)
           System.out.println("从"+start+"出发到"+i+"的最短路径为:"+path[i]);  
         System.out.println("=====================================");
      
        return shortPath;
    }
}



对于下图:


运行结果:
从0出发到0的最短路径为:0-->0
从0出发到1的最短路径为:0-->1
从0出发到2的最短路径为:0-->3-->2
从0出发到3的最短路径为:0-->3
从0出发到4的最短路径为:0-->3-->2-->4
=====================================
从0出   发到0的最短距离为:0
从0出   发到1的最短距离为:10
从0出   发到2的最短距离为:50
从0出   发到3的最短距离为:30
从0出   发到4的最短距离为:60

下载源码:
  • 大小: 42.3 KB
分享到:
评论

相关推荐

    java算法分析与设计之单源最短路径(Dijkstra算法)源代码

    java算法分析与设计之单源最短路径(Dijkstra算法)源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络...

    单源最短路径 直接copy 运行即可,里面有测试结果

    本篇文章将深入探讨单源最短路径的概念、Dijkstra算法的原理,并通过一个具体的Java实现案例来理解其实际应用。 #### 单源最短路径概念 单源最短路径问题旨在找到一个加权图中从给定源节点到其余所有节点的最短...

    求单源最短路径(算法分析中)c++

    在实际应用中,单源最短路径算法不仅限于C++,也可以在其他编程语言中实现,如Java、Python等。无论使用哪种语言,理解算法背后的逻辑和数据结构是至关重要的,这将帮助你更有效地解决问题并进行代码实现。

    三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。

    其次,Dijkstra算法由荷兰计算机科学家艾兹格·迪科斯彻提出,主要用于寻找单源最短路径。Dijkstra算法采用贪心策略,每次选择当前未访问节点中距离源点最近的一个加入到最短路径集合中。它保证了路径的正确性,但不...

    单源最短路径

    Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出的,主要用于解决单源最短路径问题。它保证找到的路径是最优的,即每次扩展的边都是当前未访问节点中最短的。Dijkstra算法的基本思想是使用优先队列...

    java单源最短路径(贪心算法)

    java单源最短路径(贪心算法) public class TheShortestWay { static int MAX_SIZE = 6; public static void dijkstra(int v, float[][] a, float[] dist, int[] prev) { int n = dist.length - 1; if (v ||...

    java实现单源最短路径

    "java实现单源最短路径" java实现单源最短路径是使用java语言实现的单源最短路径算法。该算法使用Dijkstra算法,采用邻接表表示图,通过构建邻接表来实现单源最短路径的计算。 单源最短路径算法是一种常用的图算法...

    java解决单源最短路径

    由Dijkstra贪心算法实现,设置顶点集合实现贪心扩充直到找到源点到所有顶点的路径长度;用dist数组记录当前从源到顶点的最短特殊路径长度

    单源最短路径算法(MapReduce)源代码

    本篇文章主要解析一个关于单源最短路径(Single Source Shortest Path, SSSP)算法在MapReduce框架下的实现源代码。单源最短路径问题是指在一个带有权重的有向图或无向图中找到从一个指定的起点到所有其他顶点的最短...

    java单源最短路径源程序文件

    3. **Dijkstra算法**:Dijkstra算法是最常用的解决单源最短路径问题的算法,由Edsger W. Dijkstra提出。它通过维护一个优先队列,逐步找到从源点到各个顶点的最短路径。每次从队列中取出距离源点最近的顶点,并更新...

    java 无向图所有最短路径算法的实现

    Dijkstra算法是最常用的单源最短路径算法,用于找到图中一个顶点到其他所有顶点的最短路径。在无向图中,Dijkstra算法通过维护一个优先队列(通常是二叉堆)来逐步扩展最短路径树。每次从队列中取出距离源点最近的...

    Dijkstra最短路径算法

    **Dijkstra最短路径算法**是图论中的一个重要算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出,主要用于解决单源最短路径问题。这个算法能够找到图中一个起点到其他所有顶点的最短路径,尤其适用于有向图或无...

    图的结构建立与最短路径算法

    Dijkstra算法是一种解决有向图中单源最短路径问题的高效算法,前提条件是图中所有边的权重必须是非负的。该算法的核心思想是使用贪心策略,逐步扩展从源点出发的最短路径。算法维护了一个集合S,包含了已找到最短...

    java使用Dijkstra算法实现单源最短路径

    java使用Dijkstra算法实现单源最短路径 Dijkstra算法是解决单源最短路径问题的经典算法,该算法由荷兰计算机科学家Edsger W. Dijkstra于1959年提出。单源最短路径问题是指在图中找出从给定顶点到其它任一顶点的最短...

    最短路径(单源多源等形式).rar

    在这个压缩包中,包含的文件主要围绕两种算法来解决这一问题:单源最短路径算法Dijkstra和多源最短路径算法Floyd-Warshall,以及它们在不同数据结构上的实现。 1. Dijkstra算法:由荷兰计算机科学家艾兹格·迪科斯...

    Dijkstra算法java实现

    总的来说,Dijkstra算法是解决单源最短路径问题的有效工具,通过合理的数据结构和巧妙的优化策略,可以在Java等编程语言中高效实现。理解并掌握这个算法,对于学习图论和算法设计具有重要意义。

    Dijkstra算法找最短路径代码_dijkstra_Dijkstra算法找最短路径代码_dijkstra算法_

    Dijkstra算法,由荷兰计算机科学家艾兹格·迪科斯彻于1956年提出,是一种用于在图中寻找单源最短路径的算法。它适用于加权有向图或无向图,且所有边的权重都是非负的。这个算法的核心思想是通过逐步扩展最短路径树来...

    dijkstra算法实现两景点间最短路径

    数据结构课程实践:1. 问题描述: 以顶点表示校平面图中各景点,要有景点名称、代号、简介等信息;以边表示路径,存放路径长度等...(2)解决单源点最短路径问题;(3)任意两个景点之间的最短路径。 我用java实现的

Global site tag (gtag.js) - Google Analytics