本文举例说明了用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)。节点v0在g中指定，需要找出(或指出它不存在)连接vj的最短有向路径(vj从v0到g.Dijstra算法采用贪婪策略，从源点开始，通过连通点不断寻找到其他点的最短距离。

Dijkstra的贪婪应用程序利用(2)中的属性，不断选择“最近”的节点并探测每个节点的所有可能链接，并从起点向外扩展到终点。至于源点a，逐渐展开，根据dist [j]=min {dist [j]，dist [I]矩阵[I] [j]}，更新与I直接相邻的顶点信息。

算法描述

1)算法思想：

设G=(V，E)为加权有向图，将顶点集V分成两组。第一组是已经找到最短路径的顶点集(用S表示，开始S中只有一个源点，每条最短路径都会被加入到集合S中，直到所有顶点都加入到S中，算法结束)。第二组是尚未确定最短路径的顶点集(用U表示，在连接过程中，始终保持从源点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边上的权重.

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

四、算法PHP实现

？phpclass Dijkstra { private $ G；public function __construct() { //有向图存储$this-G=array(array(0，1，2，0，0，0，0，0，1，2，0，0，0，2，0)，array(0，0，0，1，3)，array(0，0，0，0，0，0，0，3)，array(0，0，0，0，0，0，0，1)，array(0，0，0，0，0，)公共函数计算(){ //存储已经选择节点和剩余节点$U=数组(0);$V=数组(1,2,3,4,5,6);//存储路径上节点距离源点的最小距离$ d=array()；//初始化图中节点与源点0的最小距离for($ I=1；$ i7 $ I){ if($ this-G[0][$ I]0){ $ d[$ I]=$ this-G[0][$ I]；} else { $ d[$ I]=1000000；} } //n-1次循环完成转移节点任务for($ l=0；$ 16;$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作为$ k=$ u){ echo $ k . '=' .$ u . " br} }}?调用类：

$D=新Dijkstra $ D-calculate()；执行结果：

1=12=23=24=35=36=4更多关于服务器端编程语言(专业超文本预处理器的缩写)相关内容感兴趣的读者可查看本站专题： 《PHP数据结构与算法教程》 、 《PHP基本语法入门教程》 、 《php面向对象程序设计入门教程》 、 《php字符串(string)用法总结》 及《php查找技巧与方法总结》

希望本文所述对大家服务器端编程语言(专业超文本预处理器的缩写)程序设计有所帮助。