PHP实现的迪科斯彻(Dijkstra)最短路径算法实例

本文实例讲述了PHP实现的迪科斯彻(Dijkstra)最短路径算法。分享给大家供大家参考,具体如下:

一、待解决问题

单源最短路径问题,在给定有向图中求一个顶点(单源顶点)到其他所有顶点的最短路径问题。在下图中,每条边上有一个权值,希望求解A到所有其他顶点(B/C/D/E/F/G)的最短路径。

二、问题分析(最短路径的子结构同样最优性)

如果P(A,G)是从顶点A到G的最短路径,假设D和F是这条路径上的中间点,那么P(D,F)一定时从D到F的最短路径。如果P(D,F)不是D到F的最短路径,那必然存在某一个节点M的另一条D到F的路径可以使P(A,B...M...F,G)比P(A,G)小,自相矛盾。

有了这样的性质,我们可以了解Dijkstra算法。

三、Dijkstra算法

Dijkstra 算法,又叫迪科斯彻算法(Dijkstra),又称为单源最短路径算法,所谓单源是在一个有向图中,从一个顶点出发,求该顶点至所有可到达顶点的最短路径问题。 问题描述为设G=(V,E)是一个有向图,V表示顶点,E表示边。它的每一条边(i,j)属于E,都有一个非负权W(I,j),在G中指定一个结点v0,要求把从v0到G的每一个接vj(vj属于V)的最短有向路径找出来(或者指出不存在)。 Dijstra算法是运用贪心的策略,从源点开始,不断地通过相联通的点找出到其他点的最短距离。

Dijkstra的贪心应用在他利用(二)中的性质,不断地选取“最近”的节点并试探每个节点的所有可能存在链接,以起始点为中心向外层层扩展,直到扩展到终点为止。对于源点A,逐步扩展,根据dist[j]=min{dist[j],dist[i]+matrix[i][j]}更新与i直接相邻的顶点信息。

算法描述

1)算法思想:

设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

2)算法步骤:

a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则<u,v>正常有权值,若u不是v的出边邻接点,则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。

c.以k为新考虑的中间点,修改U中与k相邻的各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值为顶点k的距离加上k与u边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

四、算法PHP实现

<?php
class Dijkstra
{
  private $G;
  public function __construct()
  {
    //有向图存储
    $this->G = array(
      array(0,1,2,0,0,0,0),
      array(0,0,0,1,2,0,0),
      array(0,0,0,0,0,2,0),
      array(0,0,0,0,0,1,3),
      array(0,0,0,0,0,0,3),
      array(0,0,0,0,0,0,1),
      array(0,0,0,0,0,0,0),
    );
  }
  public function calculate()
  {
    // 存储已经选择节点和剩余节点
    $U = array(0);
    $V = array(1,2,3,4,5,6);
    // 存储路径上节点距离源点的最小距离
    $d = array();
    //初始化图中节点与源点0的最小距离
    for($i=1;$i<7;$i++)
    {
      if($this->G[0][$i]>0)
      {
        $d[$i] = $this->G[0][$i];
      }
      else
      {
        $d[$i] = 1000000;
      }
    }
    // n-1次循环完成转移节点任务
    for($l=0;$l<6;$l++)
    {
      // 查找剩余节点中距离源点最近的节点v
      $current_min = 100000;
      $current_min_v = 0;
      foreach($V as $k=>$v)
      {
        if($d[$v] < $current_min)
        {
          $current_min = $d[$v];
          $current_min_v = $v;
        }
      }
      //从V中更新顶点到U中
      array_push($U,$current_min_v);
      array_splice($V,array_search($current_min_v,$V),1);
      //更新
      foreach($V as $k=>$u)
      {
        if($this->G[$current_min_v][$u]!=0&&$d[$u]>$d[$current_min_v]+$this->G[$current_min_v][$u])
        {
          $d[$u] = $d[$current_min_v]+$this->G[$current_min_v][$u];
        }
      }
    }
    foreach($d as $k => $u)
    {
      echo $k.'=>'.$u.'<br>';
    }
  }
}
?>

调用类:

$D = new Dijkstra;
$D->calculate();

执行结果:

1=>1
2=>2
3=>2
4=>3
5=>3
6=>4

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》及《php查找技巧与方法总结》

希望本文所述对大家PHP程序设计有所帮助。

(0)

相关推荐

  • PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例

    队列这种数据结构更简单,就像我们生活中排队一样,它的特性是先进先出(FIFO). PHP SPL中SplQueue类就是实现队列操作,和栈一样,它也可以继承双链表(SplDoublyLinkedList)轻松实现. SplQueue类摘要如下: SplQueue简单使用如下: 复制代码 代码如下: $queue = new SplQueue();   /**  * 可见队列和双链表的区别就是IteratorMode改变了而已,栈的IteratorMode只能为:  * (1)SplDoublyL

  • PHP基于递归实现的约瑟夫环算法示例

    本文实例讲述了PHP基于递归实现的约瑟夫环算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php $nu

  • PHP实现二叉树的深度优先与广度优先遍历方法

    本文实例讲述了PHP实现二叉树的深度优先与广度优先遍历方法.分享给大家供大家参考.具体如下: #二叉树的广度优先遍历 #使用一个队列实现 class Node { public $data = null; public $left = null; public $right = null; } #@param $btree 二叉树根节点 function breadth_first_traverse($btree) { $traverse_data = array(); $queue = arr

  • PHP实现的回溯算法示例

    本文实例讲述了PHP实现的回溯算法.分享给大家供大家参考,具体如下: 问题: 一头大牛驼2袋大米,一头中牛驼一袋大米,两头小牛驼一袋大米,请问100袋大米需要多少头大牛,多少头中牛,多少头小牛? 实现代码: <?php /* * k = 2x + y + 1/2z 取值范围 * 0 <= x <= 1/2k * 0 <= y <= k * 0 <= z < = 2k * x,y,z最大值 2k */ $daMi = 100; $result = array();

  • PHP二分查找算法的实现方法示例

    本文实例讲述了PHP二分查找算法的实现方法.分享给大家供大家参考,具体如下: 二分查找法需要数组是一个有序的数组 假设我们的数组是一个递增的数组,首先我们需要找到数组的中间位置. 1. 要知道中间位置就需要知道起始位置和结束位置,然后取出中间位置的值来和我们的值做对比. 2. 如果中间值大于我们的给定值,说明我们的值在中间位置之前,此时需要再次二分,因为在中间之前,所以我们需要变的值是结束位置的值,此时结束位置的值应该是我们此时的中间位置. 3. 反之,如果中间值小于我们给定的值,那么说明给定值

  • PHP使用栈解决约瑟夫环问题算法示例

    本文实例讲述了PHP使用栈解决约瑟夫环问题算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php cla

  • PHP实现广度优先搜索算法(BFS,Broad First Search)详解

    本文实例讲述了PHP实现广度优先搜索算法.分享给大家供大家参考,具体如下: 广度优先搜索的算法思想 Breadth-FirstTraversal 广度优先遍历是连通图的一种遍历策略.因为它的思想是从一个顶点V0开始,辐射状地优先遍历其周围较广的区域,故得名. 广度优先搜索遍历类似于树的按层次遍历.对于无向连通图,广度优先搜索是从图的某个顶点v0出发,在访问v0之后,依次搜索访问v0的各个未被访问过的邻接点w1,w2,-.然后顺序搜索访问w1的各未被访问过的邻接点,w2的各未被访问过的邻接点,-.

  • PHP实现找出有序数组中绝对值最小的数算法分析

    本文实例讲述了PHP实现找出有序数组中绝对值最小的数算法.分享给大家供大家参考,具体如下: 问题: 一个有序数组,值有可能有负值,也有可能没有,现需要找出其中绝对值最小的值. 方法1: 遍历数组,找到绝对值最小值,时间复杂度O(n),n为元素个数. 方法2: 二分查找,因为数组有序,可以利用二分查找,时间复杂度O(logn). 分析步骤: 1. 如果第一个数为正数,说明整个数组没有负数,直接返回第一个数 2. 如果最后一个数为负数,说明整个数组没有正数,直接返回最后一个数 3. 数组元素有正有负

  • PHP数据分析引擎计算余弦相似度算法示例

    本文实例讲述了PHP数据分析引擎计算余弦相似度算法.分享给大家供大家参考,具体如下: 关于余弦相似度的相关介绍可参考百度百科:余弦相似度 <?php /** * 数据分析引擎 * 分析向量的元素 必须和基准向量的元素一致,取最大个数,分析向量不足元素以0填补. * 求出分析向量与基准向量的余弦值 * @author yu.guo@okhqb.com */ /** * 获得向量的模 * @param unknown_type $array 传入分析数据的基准点的N维向量.|eg:array(1,1

  • 基于PHP实现栈数据结构和括号匹配算法示例

    本文实例讲述了基于PHP实现栈数据结构和括号匹配算法.分享给大家供大家参考,具体如下: 栈,体现的是后进先出,即LIFO.队列,体现的是先进先出,即FIFO. 栈操作: array_pop() //尾出 array_push() //尾进 或 array_shift()//头进 array_unshift()//头出 用例:验证一个数学算式是否正确,比如{2*3[x*y+5+m*(i-j)/3]+k*(4+(t+9))}. 分析:对于一个算式的正确与否,就是体现在,各种括号的匹配上,括号完全匹配

  • PHP实现深度优先搜索算法(DFS,Depth First Search)详解

    本文实例讲述了PHP实现深度优先搜索算法.分享给大家供大家参考,具体如下: 深度优先搜索的实现原理: 实现代码: <?php class Search_Method { //无向图的数组描述 private $dfs_save; //全局记录数组 private $arr; //控制分支- private $k = 0; public function __construct() { $this->dfs_save = array( array(0,1,1,1,0,0,0,0,0), arra

随机推荐