`
Eastsun
  • 浏览: 309412 次
  • 性别: Icon_minigender_1
  • 来自: 天津
社区版块
存档分类
最新评论

使用基于邻接表的Dijkstra算法求解Project Euler问题

算法ScalaPHP.netUP 
阅读更多
Project Euler中的几个问题

　　首先，来看一看Project Euler上的第81到83题。这几个题目的前提条件是一样的，已知一个80×80的矩阵(由正整数组成)
　　81题：Find the minimal path sum, in the 80 by 80 matrix, from the top left to the bottom right by only moving right and down.
　　其意思是：只允许从上往下或从左到右，找一条从这个矩阵左上角到右下角的路径，使得路径上的数字之和最小。

　　82题：Find the minimal path sum, in the 80 by 80 matrix, from the left column to the right column,by only moving up, down, and right.
　　该题的意思是：允许从上到下或从下到上或从左到右移动，找一条从该矩阵最左列到最右列的路径，使得路径上的数字之和最小。

　　83题：Find the minimal path sum, in the 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.
　　翻译过来就是：可以上下左右移动，找一条从该矩阵左上角到右下角的路径，使得路径上数字之和最小。

　　这几个题非常类似，都是从一个给定矩阵找一条路径使得上面数字之和最小。只不过移动的方式越来越多，因此可以想象这几个题目的难度也是越来越大。如果对动态规划比较熟悉的话，很容易可以看出81与82题是可以使用动态规划来解决的。只不过81题属于典型的动态规划题，很容易写出代码，而82题稍稍麻烦了一点。
　　不过这里我不谈怎么使用动态规划来解决这些问题，而是转换一下考察问题的角度，将这几个问题转换成图论中经典的“最短路”问题，然后可以使用同样的方法完美解决之。
　　首先，将80×80的矩阵看成一个80×80个顶点的图，如果能够从矩阵(i,j)移动到(u,v)，则用一条(i,j)到(u,v)的边将这两个顶点连接起来，并且该边的权即为矩阵在(u,v)处的取值。这样，就将一个矩阵转换为一个带权的有向图。并且容易看出，题目中要求的“数字之和最小的路径”对应该有向图的一个“最短路”。这三个题的区别只在于顶点与顶点之间连接的边不一样。


Dijkstra算法与实现

　　图论中关于求“最短路”问题的算法有很多，著名的有Floyd-Warshall算法，Bellman-Ford 算法etc。不过，Floyd-Warshall算法虽然实现简单，但时间复杂度是O(n^3)，而这里n = 80*80 = 6400，使用Floyd-Warshall算法时间上无法接受。另外，这三个题中涉及到的有向图都属于稀疏图，所以我采用了基于图的邻接表结构的Dijkstra算法，这个实现的时间复杂度是O(e×log e)，其中e表示边的条数。由于这三个题中e = O(v)（v指图的顶点个数），因此最后我们得到了时间复杂度为O(v log v)的解法（这些题中，v = 80*80）。下面是使用Scala实现的Dijkstra算法： 
/**
  &#Graph.scala
  utils for graph algorithm
  @author Eastsun
*/
package eastsun.math

object Graph {
    /**
      This is an implementation of Dijkstra's algorithm to find the shortest path for a directed
      graph with non-negative edge weights.
    */
    def dijkstra(size :Int,start :Int,lst :Int=> Iterable[(Int,Int)]):Array[Int] = {
        import java.lang.Integer.{ MAX_VALUE => INF }
        implicit def t2o(t :(Int,Int)) = new Ordered[(Int,Int)]{
            def compare(that :(Int,Int)) = that._2 - t._2
        }
        val pq = new scala.collection.mutable.PriorityQueue[(Int,Int)]
        val dist = Array.make(size,INF)
        val mark = Array.make(size,false)
        pq += start->0
        while(!pq.isEmpty){
            val (idx,dst) = pq.dequeue
            if(!mark(idx)){
                mark(idx) = true
                dist(idx) = dst
                for((i,d) <- lst(idx);if dist(i)>dst+d){
                    dist(i) = dst+d
                    pq += i->dist(i)
                }                
            }
        }
        dist   
    }
}

　　考虑到对Scala熟悉的不多，我简单解释一下上面这段代码。首先，函数 
    def dijkstra(size :Int,start :Int,lst :Int=> Iterable[(Int,Int)]):Array[Int]

有三个参数，其中：
　　　　size　　　 表示要考虑的有向图的阶（也就是顶点个数）
　　　　start　　　 要求的最短路的起始点
　　　　lst　　　　 一个参数为Int返回值为Iterable[(Int,Int)]的函数。lst(k)将返回图的第k个顶点对应的邻接表，邻接表的每个节点保存两个值(idx,dst)。其中idx表示顶点k到顶点idx有一条边，dst表示这条边的权值。
返回值为一个整型数组Array[Int]，该数组保存了最终结果，其长度为size，第k个元素的值表示从顶点start到顶点k的最短距离，如果不能到达，则为Integer.MAX_VALUE。

　　其次，看一下这段代码： 
        implicit def t2o(t :(Int,Int)) = new Ordered[(Int,Int)]{
            def compare(that :(Int,Int)) = that._2 - t._2
        }
        val pq = new scala.collection.mutable.PriorityQueue[(Int,Int)]

这段代码的功能是new了一个优先队列pq，该优先队列里面保存的数据类型为(idx,dst)。其中idx为顶点的序号，而dst为距离。并且规定了一个顺序Ordered[(Int,Int)]，使得优先队列保持dst最小的在最上面。
　　可以计算，上面的Dijkstra实现的时间复杂度为O(e log e)。


解题代码
　　有了上面的介绍，下面直接给出Project Euler这几个问题的代码，可以看到，这几个问题的解题代码非常一致（82题略有不同）
81题的解题代码： 
import eastsun.math.Graph._
import scala.io.Source._

object Euler081 extends Application {
    val mtx = fromFile("matrix.txt").getLines.map{ line =>
                  line.split(",").map(_.trim.toInt)
              }.toList.toArray
  
    val LEN = mtx.size
    val SIZE = LEN*LEN
    def lst(n :Int):List[(Int,Int)] = {
        val (x,y) = (n/LEN,n%LEN)
        var ls = Nil:List[(Int,Int)]
        if(x < LEN-1) ls = (n+LEN,mtx(y)(x+1))::ls
        if(y < LEN-1) ls = (n+1,mtx(y+1)(x))::ls
        ls
    }
    println(dijkstra(SIZE,0,lst)(SIZE-1)+mtx(0)(0))
}


82题的解题代码： 
import scala.io.Source._
import eastsun.math.Graph._

object Euler082 extends Application {
    val mtx = fromFile("matrix.txt").getLines.map{ line =>
                  line.split(",").map(_.trim.toInt)
              }.toList.toArray
    val LEN = mtx.size
    val SIZE = LEN*LEN
    def lst(n :Int):List[(Int,Int)] = {
        val (x,y) = (n/LEN,n%LEN)
        var ls = Nil:List[(Int,Int)]
        if(y > 0)     ls = (n-1,mtx(y-1)(x))::ls
        if(y < LEN-1) ls = (n+1,mtx(y+1)(x))::ls
        if(x < LEN-1) ls = (n+LEN,mtx(y)(x+1))::ls
        ls
    }
    val res = 0.until(LEN).map{ n =>
                  dijkstra(SIZE,n,lst).slice(SIZE-LEN,SIZE).reduceLeft(_ min _)+mtx(n)(0)
              }.reduceLeft(_ min _)
    println(res)
}


83题的解题代码： 
import scala.io.Source._
import eastsun.math.Graph._

object Euler083 extends Application {
    val mtx = fromFile("matrix.txt").getLines.map{ line =>
                  line.split(",").map(_.trim.toInt)
              }.toList.toArray
    val LEN = mtx.size
    val SIZE = LEN*LEN
    def lst(n :Int):List[(Int,Int)] = {
        val (x,y) = (n/LEN,n%LEN)
        var ls = Nil:List[(Int,Int)]
        if(y > 0)     ls = (n-1,mtx(y-1)(x))::ls
        if(y < LEN-1) ls = (n+1,mtx(y+1)(x))::ls
        if(x > 0)     ls = (n-LEN,mtx(y)(x-1))::ls
        if(x < LEN-1) ls = (n+LEN,mtx(y)(x+1))::ls
        ls
    }

    println(dijkstra(SIZE,0,lst)(SIZE-1)+mtx(0)(0))
}
分享到：
| 连分数及Pell方程的解法
评论
5 楼 Eastsun 2008-12-06  
用Scala可以简化一些代码，而且Scala的性能和原生Java差不多
4 楼 pipilu 2008-12-05  
想问一下楼主，为什么选择skala语言？
3 楼 shuchaoo 2008-11-06  
Eastsun 写道
Project Euler中的几个问题

　　首先，来看一看Project Euler上的第81到83题。这几个题目的前提条件是一样的，已知一个80×80的矩阵(由正整数组成)
　　81题：Find the minimal path sum, in the 80 by 80 matrix, from the top left to the bottom right by only moving right and down.
　　其意思是：只允许从上往下或从左到右，找一条从这个矩阵左上角到右下角的路径，使得路径上的数字之和最小。

　　82题：Find the minimal path sum, in the 80 by 80 matrix, from the left column to the right column,by only moving up, down, and right.
　　该题的意思是：允许从上到下或从下到上或从左到右移动，找一条从该矩阵最左列到最右列的路径，使得路径上的数字之和最小。

　　83题：Find the minimal path sum, in the 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.
　　翻译过来就是：可以上下左右移动，找一条从该矩阵左上角到右下角的路径，使得路径上数字之和最小。

　　这几个题非常类似，都是从一个给定矩阵找一条路径使得上面数字之和最小。只不过移动的方式越来越多，因此可以想象这几个题目的难度也是越来越大。如果对动态规划比较熟悉的话，很容易可以看出81与82题是可以使用动态规划来解决的。只不过81题属于典型的动态规划题，很容易写出代码，而82题稍稍麻烦了一点。
　　不过这里我不谈怎么使用动态规划来解决这些问题，而是转换一下考察问题的角度，将这几个问题转换成图论中经典的“最短路”问题，然后可以使用同样的方法完美解决之。
　　首先，将80×80的矩阵看成一个80×80个顶点的图，如果能够从矩阵(i,j)移动到(u,v)，则用一条(i,j)到(u,v)的边将这两个顶点连接起来，并且该边的权即为矩阵在(u,v)处的取值。这样，就将一个矩阵转换为一个带权的有向图。并且容易看出，题目中要求的“数字之和最小的路径”对应该有向图的一个“最短路”。这三个题的区别只在于顶点与顶点之间连接的边不一样。


Dijkstra算法与实现

　　图论中关于求“最短路”问题的算法有很多，著名的有Floyd-Warshall算法，Bellman-Ford 算法etc。不过，Floyd-Warshall算法虽然实现简单，但时间复杂度是O(n^3)，而这里n = 80*80 = 6400，使用Floyd-Warshall算法时间上无法接受。另外，这三个题中涉及到的有向图都属于稀疏图，所以我采用了基于图的邻接表结构的Dijkstra算法，这个实现的时间复杂度是O(e×log e)，其中e表示边的条数。由于这三个题中e = O(v)（v指图的顶点个数），因此最后我们得到了时间复杂度为O(v log v)的解法（这些题中，v = 80*80）。下面是使用Scala实现的Dijkstra算法： 
/**
  &#Graph.scala
  utils for graph algorithm
  @author Eastsun
*/
package eastsun.math

object Graph {
    /**
      This is an implementation of Dijkstra's algorithm to find the shortest path for a directed
      graph with non-negative edge weights.
    */
    def dijkstra(size :Int,start :Int,lst :Int=> Iterable[(Int,Int)]):Array[Int] = {
        import java.lang.Integer.{ MAX_VALUE => INF }
        implicit def t2o(t :(Int,Int)) = new Ordered[(Int,Int)]{
            def compare(that :(Int,Int)) = that._2 - t._2
        }
        val pq = new scala.collection.mutable.PriorityQueue[(Int,Int)]
        val dist = Array.make(size,INF)
        val mark = Array.make(size,false)
        pq += start->0
        while(!pq.isEmpty){
            val (idx,dst) = pq.dequeue
            if(!mark(idx)){
                mark(idx) = true
                dist(idx) = dst
                for((i,d) <- lst(idx);if dist(i)>dst+d){
                    dist(i) = dst+d
                    pq += i->dist(i)
                }                
            }
        }
        dist   
    }
}

　　考虑到对Scala熟悉的不多，我简单解释一下上面这段代码。首先，函数 
    def dijkstra(size :Int,start :Int,lst :Int=> Iterable[(Int,Int)]):Array[Int]

有三个参数，其中：
　　　　size　　　 表示要考虑的有向图的阶（也就是顶点个数）
　　　　start　　　 要求的最短路的起始点
　　　　lst　　　　 一个参数为Int返回值为Iterable[(Int,Int)]的函数。lst(k)将返回图的第k个顶点对应的邻接表，邻接表的每个节点保存两个值(idx,dst)。其中idx表示顶点k到顶点idx有一条边，dst表示这条边的权值。
返回值为一个整型数组Array[Int]，该数组保存了最终结果，其长度为size，第k个元素的值表示从顶点start到顶点k的最短距离，如果不能到达，则为Integer.MAX_VALUE。

　　其次，看一下这段代码： 
        implicit def t2o(t :(Int,Int)) = new Ordered[(Int,Int)]{
            def compare(that :(Int,Int)) = that._2 - t._2
        }
        val pq = new scala.collection.mutable.PriorityQueue[(Int,Int)]

这段代码的功能是new了一个优先队列pq，该优先队列里面保存的数据类型为(idx,dst)。其中idx为顶点的序号，而dst为距离。并且规定了一个顺序Ordered[(Int,Int)]，使得优先队列保持dst最小的在最上面。
　　可以计算，上面的Dijkstra实现的时间复杂度为O(e log e)。


解题代码
　　有了上面的介绍，下面直接给出Project Euler这几个问题的代码，可以看到，这几个问题的解题代码非常一致（82题略有不同）
81题的解题代码： 
import eastsun.math.Graph._
import scala.io.Source._

object Euler081 extends Application {
    val mtx = fromFile("matrix.txt").getLines.map{ line =>
                  line.split(",").map(_.trim.toInt)
              }.toList.toArray
  
    val LEN = mtx.size
    val SIZE = LEN*LEN
    def lst(n :Int):List[(Int,Int)] = {
        val (x,y) = (n/LEN,n%LEN)
        var ls = Nil:List[(Int,Int)]
        if(x < LEN-1) ls = (n+LEN,mtx(y)(x+1))::ls
        if(y < LEN-1) ls = (n+1,mtx(y+1)(x))::ls
        ls
    }
    println(dijkstra(SIZE,0,lst)(SIZE-1)+mtx(0)(0))
}


82题的解题代码： 
import scala.io.Source._
import eastsun.math.Graph._

object Euler082 extends Application {
    val mtx = fromFile("matrix.txt").getLines.map{ line =>
                  line.split(",").map(_.trim.toInt)
              }.toList.toArray
    val LEN = mtx.size
    val SIZE = LEN*LEN
    def lst(n :Int):List[(Int,Int)] = {
        val (x,y) = (n/LEN,n%LEN)
        var ls = Nil:List[(Int,Int)]
        if(y > 0)     ls = (n-1,mtx(y-1)(x))::ls
        if(y < LEN-1) ls = (n+1,mtx(y+1)(x))::ls
        if(x < LEN-1) ls = (n+LEN,mtx(y)(x+1))::ls
        ls
    }
    val res = 0.until(LEN).map{ n =>
                  dijkstra(SIZE,n,lst).slice(SIZE-LEN,SIZE).reduceLeft(_ min _)+mtx(n)(0)
              }.reduceLeft(_ min _)
    println(res)
}


83题的解题代码： 
import scala.io.Source._
import eastsun.math.Graph._

object Euler083 extends Application {
    val mtx = fromFile("matrix.txt").getLines.map{ line =>
                  line.split(",").map(_.trim.toInt)
              }.toList.toArray
    val LEN = mtx.size
    val SIZE = LEN*LEN
    def lst(n :Int):List[(Int,Int)] = {
        val (x,y) = (n/LEN,n%LEN)
        var ls = Nil:List[(Int,Int)]
        if(y > 0)     ls = (n-1,mtx(y-1)(x))::ls
        if(y < LEN-1) ls = (n+1,mtx(y+1)(x))::ls
        if(x > 0)     ls = (n-LEN,mtx(y)(x-1))::ls
        if(x < LEN-1) ls = (n+LEN,mtx(y)(x+1))::ls
        ls
    }

    println(dijkstra(SIZE,0,lst)(SIZE-1)+mtx(0)(0))
}

这种代码要手写才有劲！不带变成环境！
2 楼 joyo2008 2008-10-07  
谢谢  学习了
1 楼 fkpwolf 2008-10-05  
天哪      
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    linjiebiao.rar_dijkstra_dijkstra算法_邻接表_邻接表 dijkstra

    在Dijkstra算法的实现中，邻接表是一种非常重要的数据结构。相较于邻接矩阵，邻接表在处理稀疏图（边的数量远小于顶点数量的平方）时，空间效率更高。邻接表由一系列链表或队列组成，每个链表或队列代表图中一个顶点...

    Dijkstra算法求解格栅地图路径matlab代码.rar

    然后，我们可以基于这个数组构建邻接矩阵或邻接表，存储地图中节点之间的连接关系。 2. 初始化距离向量和访问状态：为所有节点初始化一个距离向量，源节点距离设为0，其余节点设为无穷大。同时，创建一个访问状态...

    基于dijkstra公交最小换乘算法

    在"最小换乘.txt"这个文件中，很可能包含了实现这种算法的具体代码，包括数据结构设计（如邻接矩阵或邻接表）、节点和边的定义、距离和优先级队列的管理，以及如何处理换乘条件的逻辑。"www.pudn.com.txt"可能是提供...

    基于Dijkstra算法的最短路径问题求解.123

    ### 基于Dijkstra算法的最短路径问题求解 #### 一、Dijkstra算法简介 Dijkstra算法是由荷兰计算机科学家Edsger W. Dijkstra于1956年提出的一种用于解决加权图中单源最短路径问题的算法。该算法能够有效地找出从...

    堆优化的dijkstra算法（dijkstra+邻接表+heap）

    ### 堆优化的Dijkstra算法（Dijkstra+邻接表+Heap） #### 算法概述 Dijkstra算法是一种用于解决单源最短路径问题的著名算法，它能够找到图中某一点到其他所有点的最短路径。在处理大规模数据时，原始的Dijkstra...

    MATLAB源码集锦-基于最短路dijkstra算法离散优化问题代码

    在本资源中，我们主要关注的是使用MATLAB编程解决离散优化问题的一种经典算法——Dijkstra算法。Dijkstra算法是一种用于寻找图中两点之间最短路径的算法，它由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。在离散...

    Dijkstra算法邻接表实现

    Dijkstra算法C++邻接表实现，用邻接表存图，还有记录路径。

    Dijkstra算法求最短路径的C/C++程序一

    本程序实现了基于邻接矩阵表示的Dijkstra算法，并用C语言编写。下面将对程序的各个部分进行详细解析。 ### 程序结构与变量定义 #### 1. 基础定义 - `#define OK 1`: 定义常量`OK`为1，通常表示操作成功。 - `#...

    dijkstra算法—求解最短路问题

    ### Dijkstra算法——求解最短路径问题 #### 概述 Dijkstra算法是一种用于解决图论中最短路径问题的经典算法。它能够有效地找到两点之间的最短路径，并且被广泛应用于计算机科学、地理信息系统（GIS）、网络路由...

    Dijkstra算法求最短路径——Java实现

    - 图的表示：可能使用邻接矩阵或邻接表来存储图的数据结构。 - Dijkstra算法的实现：包括上述步骤的代码逻辑，如优先队列的使用、节点距离的更新等。 - 主函数：读取输入，构建图，调用Dijkstra算法，打印最短路径及...

    MATLAB设计_dijkstra算法求解最短路.zip

    MATLAB代码实现时，首先需要构建图的邻接矩阵或邻接表表示，然后通过循环遍历和更新节点状态来执行Dijkstra算法。在压缩包中的“dijkstra”文件很可能是MATLAB程序的主要源码，可能包含了定义图、初始化、选择节点、...

    c++课设报告《基于Dijkstra算法的最短路径问题求解》.doc

    本文档是一个关于使用C++语言实现基于Dijkstra算法的最短路径问题求解的课设报告。下面是从该报告中提取的相关知识点： 1. Dijkstra算法：Dijkstra算法是一种常用的图搜索算法，用于解决单源最短路径问题。该算法由...

    精选_毕业设计_基于Dijkstra算法的最短路径问题求解_完整源码

    【标题】"精选_毕业设计_基于Dijkstra算法的最短路径问题求解_完整源码" 提供了一个关于使用Dijkstra算法解决最短路径问题的毕业设计项目。这个项目的核心是实现一个高效的算法来找到图中两个节点之间的最短路径。 ...

    C语言实现Dijkstra算法

    首先，图在C语言中通常使用邻接矩阵或邻接表来表示。邻接矩阵是一个二维数组，其元素表示图中节点之间的连接关系。如果节点i到节点j存在边且无权值，则在矩阵中的对应位置设为1；如果有权值，则存放该权值。对于无向...

    基于Dijkstra路由算法的路由软件实现

    在Java中实现Dijkstra算法，首先需要定义图的数据结构，可以使用邻接矩阵或者邻接表来表示。接着，创建一个优先队列（如PriorityQueue）用于存储待处理的节点，根据节点距离进行排序。以下是一个简单的Java实现框架...

    利用Dijkstra算法来求解顶点之间最短路径

    本文总结了利用 Dijkstra 算法来求解顶点之间最短路径的知识点，包括问题分析、任务定义、概要设计、数据结构的选择、详细设计和编码等方面。 一、问题分析与任务定义 1. 问题分析：选择合适的结构表示图，使用 ...

    基于最短路dijkstra算法离散优化问题matlab代码.zip

    在MATLAB中，我们可以用邻接矩阵或邻接表来表示图，然后通过迭代实现Dijkstra算法。 3. 离散优化问题 离散优化问题通常涉及在有限的决策空间中寻找最佳解，例如在满足约束条件下最大化或最小化某个目标函数。...

    dijkstra算法 C++ 堆排序 邻接表实现

    在C++中实现Dijkstra算法和堆排序，首先需要定义图的数据结构，一般可以使用邻接矩阵或邻接表。邻接表在表示稀疏图时更节省空间。然后，可以使用`priority_queue`来存储节点及其距离，每次取出距离最小的节点进行...

    Dijkstra算法求解机器人路径规划问题Python程序

    Dijkstra算法是一种解决单源最短路径问题的算法，适用于带权的有向图或无向图。它采用贪心策略，逐步找到从源点到其他所有顶点的最短路径。 Dijkstra算法的基本思路是以起始点为中心，向外层层扩展，直到覆盖所有...

    Dijkstra算法解决最短线路问题

    在应用Dijkstra算法时，首先需要将这些数据转化为图的结构，可以使用邻接矩阵或者邻接表来表示，然后利用这些数据来计算最短路径。 **in.txt**文件可能是输入数据，可能包含了一些测试案例或者问题的具体描述，比如...

Magicbox
Global site tag (gtag.js) - Google Analytics