<?php

// 定义节点类
class Node
{
    public $name; // 节点名称
    public $connections = []; // 邻接节点列表

    public function __construct($name)
    {
        $this->name = $name;
    }

    public function addConnection($node, $distance)
    {
        $this->connections[$node->name] = $distance;
        $node->connections[$this->name] = $distance;
    }
}

// 贪心算法求解最短路径
function findShortestPath($startNode, $endNode)
{
    $pathList = []; // 路径列表
    $currentPath = []; // 当前路径

    $currentPath[] = $startNode;

    while (!empty($currentPath)) {
        $currentNode = end($currentPath);

        // 判断是否到达目标节点
        if ($currentNode === $endNode) {
            $pathList[] = $currentPath;
            array_pop($currentPath);
            continue;
        }

        // 获取节点的邻接节点列表
        $connections = $currentNode->connections;

        // 选择路径最短的邻接节点
        $nextNode = null;
        $minDistance = INF;
        foreach ($connections as $nodeName => $distance) {
            if (!in_array($nodeName, $currentPath) && $distance < $minDistance) {
                $nextNode = new Node($nodeName);
                $minDistance = $distance;
            }
        }

        if ($nextNode !== null) {
            $currentPath[] = $nextNode;
        } else {
            array_pop($currentPath);
        }
    }

    // 从路径列表中选择最短的路径
    $minPath = null;
    $minDistance = INF;
    foreach ($pathList as $path) {
        $distance = count($path) - 1;
        if ($distance < $minDistance) {
            $minPath = $path;
            $minDistance = $distance;
        }
    }

    return $minPath;
}

// 创建节点
$nodeA = new Node('A');
$nodeB = new Node('B');
$nodeC = new Node('C');
$nodeD = new Node('D');
$nodeE = new Node('E');

// 添加邻接节点
$nodeA->addConnection($nodeB, 2);
$nodeA->addConnection($nodeC, 4);
$nodeB->addConnection($nodeD, 3);
$nodeC->addConnection($nodeD, 1);
$nodeC->addConnection($nodeE, 2);
$nodeD->addConnection($nodeE, 4);

// 求解最短路径
$startNode = $nodeA;
$endNode = $nodeE;
$shortestPath = findShortestPath($startNode, $endNode);

// 输出最短路径
echo "最短路径：";
foreach ($shortestPath as $node) {
    echo $node->name . " -> ";
}
echo "结束";