单源最短路径(dijkstra算法)php实现
做一个医学项目,其中在病例评分时会用到单源最短路径的算法。单源最短路径的dijkstra算法的思路如下:
如果存在一条从i到j的最短路径(Vi.....Vk,Vj),Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。Dijkstra是以最短路径长度递增,逐次生成最短路径的算法。例如:对于源顶点V0,首先选择其直接相邻的顶点中长度最短的顶点Vi,那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+cost[i][j]}。假设G=
1.从V-U中选择使dist[i]值最小的顶点i,将i加入到U中;
2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+cost[i][j]})
3.知道U=V,停止。
利用php特有的性质,其代码如下:
function dijkstra(){ $node_info_arr=array( //结点的邻接表结构 array( 'node_id'=>0, //某个结点的id 'next_node'=>array(4,2,1), 'node_type'=>0, 'cost'=>array(10,30,100) ), array( 'node_id'=>4, //某个结点的id 'next_node'=>array(3), 'node_type'=>1, 'cost'=>array(50) ), array( 'node_id'=>3, //某个结点的id 'next_node'=>array(1), 'node_type'=>1, 'cost'=>array(10) ), array( 'node_id'=>2, //某个结点的id 'next_node'=>array(3,1), 'node_type'=>1, 'cost'=>array(60,60) ), array( 'node_id'=>1, //某个结点的id 'next_node'=>array(), 'node_type'=>2, 'cost'=>array() ) ); $start_node_id=false; //起始结点id $i_cost=array(array()); //两个节点之间的开销 $i_dist=array(); //起始点到各点的最短距离 $b_mark=array(); //是否加入了 foreach($node_info_arr as &$node_info){ if($node_info['node_type']==0){ $start_node_id=$node_info['node_id']; //找到初始节点 } foreach($node_info['next_node'] as $key=>$next_node){ $i_cost[$node_info['node_id']][$next_node]=$node_info['cost'][$key]; } $i_dist[$node_info['node_id']]='INF'; //初始化为无穷大 $b_mark[$node_info['node_id']]=false; //初始化未加入 } if($start_node_id===false){ return '302'; } //计算初始结点到各节点的最短路径 $i_dist[$start_node_id]=0; //初始点到其本身的距离为0 $b_mark[$start_node_id]=true; //初始点加入集合 $current_node_id=$start_node_id; //最近加入的节点id $node_count=count($node_info_arr); for($i=0;$i$val){ if($i_dist[$key]=='INF'||$i_dist[$key]>$i_dist[$current_node_id]+$val){ $i_dist[$key]=$i_dist[$current_node_id]+$val; } } } foreach($i_dist as $key=>$val){ if(!$b_mark[$key]){ if($val!='INF'&&($min=='INF'||$min>$val)){ $min=$val; $candidate_node_id=$key; //候选最近结点id } } } if($min=='INF'){ break; } $current_node_id=$candidate_node_id; $b_mark[$current_node_id]=true; } foreach($i_dist as $key=>$val){ echo $start_node_id.'=>'.$key.':'.$val.'<br>'; }}
其中例子为图:
运行结果为:
0=>0:0
0=>4:10
0=>3:60
0=>2:30
0=>1:70
转自: 康瑞的部落 » 单源最短路径php实现

Outils d'IA chauds

Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

AI Hentai Generator
Générez AI Hentai gratuitement.

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Dans ce chapitre, nous comprendrons les variables d'environnement, la configuration générale, la configuration de la base de données et la configuration de la messagerie dans CakePHP.

PHP 8.4 apporte plusieurs nouvelles fonctionnalités, améliorations de sécurité et de performances avec une bonne quantité de dépréciations et de suppressions de fonctionnalités. Ce guide explique comment installer PHP 8.4 ou mettre à niveau vers PHP 8.4 sur Ubuntu, Debian ou leurs dérivés. Bien qu'il soit possible de compiler PHP à partir des sources, son installation à partir d'un référentiel APT comme expliqué ci-dessous est souvent plus rapide et plus sécurisée car ces référentiels fourniront les dernières corrections de bogues et mises à jour de sécurité à l'avenir.

Pour travailler avec la date et l'heure dans cakephp4, nous allons utiliser la classe FrozenTime disponible.

Pour travailler sur le téléchargement de fichiers, nous allons utiliser l'assistant de formulaire. Voici un exemple de téléchargement de fichiers.

Dans ce chapitre, nous allons apprendre les sujets suivants liés au routage ?

CakePHP est un framework open source pour PHP. Il vise à faciliter grandement le développement, le déploiement et la maintenance d'applications. CakePHP est basé sur une architecture de type MVC à la fois puissante et facile à appréhender. Modèles, vues et contrôleurs gu

Visual Studio Code, également connu sous le nom de VS Code, est un éditeur de code source gratuit – ou environnement de développement intégré (IDE) – disponible pour tous les principaux systèmes d'exploitation. Avec une large collection d'extensions pour de nombreux langages de programmation, VS Code peut être c

Le validateur peut être créé en ajoutant les deux lignes suivantes dans le contrôleur.
