使用PHP代码实现迪杰特斯拉算法

ゞ浴缸里的玫瑰 2022-06-15 03:22 214阅读 0赞

<?php  
  
class DijkstraCommand extends CConsoleCommand\{  
  
public function run($args)  
\{  
@set\_time\_limit(0);  
@ini\_set('memory\_limit', '2048M');  
//构造数据结构  
$arcs = array(  
array(0,7,9,999,999,14),  
array(7,0,10,15,999,999),  
array(9,10,0,11,999,2),  
array(999,15,11,0,6,999),  
array(999,999,999,6,0,9),  
array(14,999,2,999,9,0)  
);  
$shortestPath = array();//最短路径值  
$checked = array();//已检查的点  
$path = array();//路径  
$dots = count($arcs);//点的数量  
for ($v = 0; $v < $dots; $v++)\{  
$checked\[$v\] = 0;  
$path\[$v\] = 0;  
$shortestPath\[$v\] = $arcs\[0\]\[$v\];  
\}  
for ($i = 0; $i < $dots; $i++)\{  
$min = 999;  
//选最短的点  
for ($w = 0; $w < $dots; $w++)\{  
if (!$checked\[$w\])  
\{  
if ($shortestPath\[$w\] < $min)\{  
$v = $w;  
$min = $shortestPath\[$w\];  
\}  
\}  
\}  
$checked\[$v\] = 1;  
//更新最短路径  
for ($w = 0; $w < $dots; $w++)\{  
if (!$checked\[$w\] && ($min + $arcs\[$v\]\[$w\] < $shortestPath\[$w\])) \{  
$shortestPath\[$w\] = $min + $arcs\[$v\]\[$w\];  
$path\[$w\] = $v;  
\}  
\}  
\}  
foreach($path as $key =>$value)\{  
$trail = "1";  
if($value > 0)\{  
$preValue = $value;  
while($value > 0)\{  
if($path\[$value\] > 0)\{  
$trail .= "->".($path\[$value\]+1);  
\}  
$value = $path\[$value\];  
\}  
$trail .= "->".($preValue+1);  
\}  
$trail .= "->".($key+1);  
echo "The trail is ".$trail." and distances is ".$shortestPath\[$key\]."\\n";  
\}  
\}  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关迪杰斯特拉算法（Java）

目录第7章迪杰斯特拉算法 7.1应用场景 7.2算法介绍 7.3 算法图解

痛定思痛。/ 2024年04月07日 15:50/ 0 赞/ 211 阅读

相关迪杰斯特拉(Dijkstra)算法

这里写目录标题 1.问题定义 2.算法思路 3.代码实现（C++） 1.问题定义给定一个带权有向图（或者无向图）G与源点v，求从源点v到G中其

待我称王封你为后i/ 2023年10月06日 16:51/ 0 赞/ 110 阅读

相关迪杰斯特拉算法

迪杰斯特拉算法迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决

╰半夏微凉°/ 2023年07月17日 14:14/ 0 赞/ 47 阅读

相关迪杰斯特拉算法

一：迪杰斯特拉算法迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思

古城微笑少年丶/ 2022年10月22日 02:46/ 0 赞/ 339 阅读

相关 1028 迪杰斯特拉算法

Description 给定n(n<=500)个顶点,以及E(E<=10000)条边，使用迪杰斯特拉算法计算顶点s到顶点t的最短路径. Input 第一行

朴灿烈づ我的快乐病毒、/ 2022年09月12日 00:57/ 0 赞/ 331 阅读

相关 Dijkstra(迪杰斯特拉)算法学习

如果要了解过程http://blog.csdn.net/cjc211322/article/details/24933909 关于路径保存方法http://blog.csdn

古城微笑少年丶/ 2022年06月15日 12:28/ 0 赞/ 357 阅读

相关使用PHP代码实现迪杰特斯拉算法

<?php class DijkstraCommand extends CConsoleCommand\{ public function run($arg

ゞ浴缸里的玫瑰/ 2022年06月15日 03:22/ 0 赞/ 215 阅读

相关迪杰特斯拉算法的代码实现

1，迪杰斯特拉算法介绍迪杰斯特拉算法是典型最短路径算法，用于计算图或网中某个特定顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外，层层扩展，直到扩展覆盖所有顶点

左手的ㄟ右手/ 2022年06月12日 09:51/ 0 赞/ 279 阅读

相关迪杰斯特拉算法（Dijkstra）证明

首先，这篇文章是在讲《图论》时候写文章（所以，还是以理论为主，以后有空的时候，会把代码发上来，不过我觉得大家看完理论，如果讲得好，代码也就比较容易了。如果讲得不好，网上

男娘i/ 2022年05月25日 04:09/ 0 赞/ 358 阅读

相关 Python实现迪杰斯特拉算法

一、迪杰斯特拉算法思想 Dijkstra算法主要针对的是有向图的单元最短路径问题，且不能出现权值为负的情况！Dijkstra算法类似于贪心算法，其应用根本在于最短路径的最

女爷i/ 2022年03月07日 14:58/ 0 赞/ 375 阅读