<?php
function sortQueue(&$q){
$sTime = [];
foreach($q as $k => $v){
$sTime[$k] = $v['sTime'];
}
uasort($q, function($a, $b) {
if ($a['sTime'] == $b['sTime']) {
return 0;
}
return ($a['sTime'] < $b['sTime']) ? -1 : 1;
});
}
function EnQueue(&$q, $node, $sTime){
$item = ['node' => $node, 'sTime' => $sTime];
array_push($q, $item);
//优先级队列
sortQueue($q);
}
function DeQueue(&$q){
$element = array_shift($q);
$node = $element['node'];
return $node;
}
function TopologicalSorting(&$g, &$sortedNode){
$nodeQueue = [];
for($i = 0; $i < $g['count']; $i++){
if($g['vertexs'][$i]['inCount'] == 0){
EnQueue($nodeQueue, $i, $g['vertexs'][$i]['sTime']);
}
}
while(!empty($nodeQueue)){
$u = DeQueue($nodeQueue);
array_push($sortedNode, $u);
for($j = 0; $j < count($g['vertexs'][$u]['edges']); $j++){
//活动边终点顶点索引
$v = $g['vertexs'][$u]['edges'][$j]['vertexIndex'];
//活动的前驱节点个数
$g['vertexs'][$v]['inCount']--;
if($g['vertexs'][$v]['inCount'] == 0){
EnQueue($nodeQueue, $v, $g['vertexs'][$v]['sTime']);
}
}
}
return count($sortedNode) == $g['count'];
}
function CalcESTime(&$g, $sortedNode){
$g['vertexs'][0]['sTime'] = 0; //est[0] = 0
foreach($sortedNode as $u){
//遍历u出发的所有有向边
foreach($g['vertexs'][$u]['edges'] as $eit){
$v = $eit['vertexIndex'];
$uvst = $g['vertexs'][$u]['sTime'] + $eit['duty'];
if($uvst > $g['vertexs'][$v]['sTime']){
$g['vertexs'][$v]['sTime'] = $uvst;
}
}
}
}
function CalcLSTime(&$g, $sortedNode){
//最后一个节点的最晚开始时间等于最早开始时间
$g['vertexs'][$g['count'] - 1]['eTime'] = $g['vertexs'][$g['count'] - 1]['sTime'];
$sortedNode = array_reverse($sortedNode);
foreach($sortedNode as $u){
//遍历u出发的所有有向边
foreach($g['vertexs'][$u]['edges'] as $eit){
$v = $eit['vertexIndex'];
$uvet = $g['vertexs'][$v]['eTime'] - $eit['duty'];
if($uvet < $g['vertexs'][$u]['eTime']){
$g['vertexs'][$u]['eTime'] = $uvet;
}
}
}
}
function CriticalPath($g){
$sortedNode = [];
//对事件顶点进行拓扑排序，得到序列的拓扑序列
if(!TopologicalSorting($g, $sortedNode)){
return false;
}
//计算事件顶点的最早开始时间
CalcESTime($g, $sortedNode);
//计算事件顶点的最晚开始时间
CalcLSTime($g, $sortedNode);
//计算活动的最早开始时间和最晚开始时间，并按照事件的拓扑顺序逐次输出关键活动，得到关键路径
foreach($sortedNode as $u){
foreach($g['vertexs'][$u]['edges'] as $eit){
$v = $eit['vertexIndex'];
//是否是关键活动？
if($g['vertexs'][$u]['sTime'] == $g['vertexs'][$v]['eTime'] - $eit['duty']){
//过滤连接事件顶点的虚拟活动边
if(!empty($eit['name'])){
echo $eit['name'].' ';
}
}
}
}
echo PHP_EOL;
return true;
}
function InitGraph(&$g, $vertex){
//图的顶点的个数
$g['count'] = $vertex;
//图的顶点列表
for($i = 0; $i < $vertex; $i++){
//事件最早开始时间
$g['vertexs'][$i]['sTime'] = 0;
//事件最晚开始时间
$g['vertexs'][$i]['eTime'] = PHP_INT_MAX;
//活动的前驱节点个数
$g['vertexs'][$i]['inCount'] = 0;
//相邻边表
$g['vertexs'][$i]['edges'] = [];
}
}
function AddGraphEdge(&$g, $name, $u, $v, $weight){
if(($u >= $g['count']) || ($v >= $g['count'])){
return false;
}
$edge = [
//活动边终点顶点索引
'vertexIndex' => $v,
//活动边的名称
'name' => $name,
//活动边的时间（权重）
'duty' => $weight
];
array_push($g['vertexs'][$u]['edges'], $edge);
$g['vertexs'][$v]['inCount']++;
return true;
}
function main(){
$graph = [];
InitGraph($graph, 10);
AddGraphEdge($graph, "P1", 0, 1, 8);
AddGraphEdge($graph, "P2", 0, 2, 5);
AddGraphEdge($graph, "", 1, 3, 0);
AddGraphEdge($graph, "", 2, 3, 0);
AddGraphEdge($graph, "P7", 1, 6, 4);
AddGraphEdge($graph, "P5", 2, 5, 7);
AddGraphEdge($graph, "P3", 3, 4, 6);
AddGraphEdge($graph, "P4", 4, 8, 4);
AddGraphEdge($graph, "P8", 6, 7, 3);
AddGraphEdge($graph, "", 8, 7, 0);
AddGraphEdge($graph, "", 8, 5, 0);
AddGraphEdge($graph, "P9", 7, 9, 4);
AddGraphEdge($graph, "P6", 5, 9, 7);
CriticalPath($graph);
return 0;
}
main();