试试这个

$arr = array_map(function($v){return $v[0];}, $graph);
$key = array_keys($arr, min($arr));

给你。

$tes = min( array_column( $graph, 0 ) );
$key = array_search( $tes, array_column( $graph, 0 ) );
$array_keys = array_keys($graph);

echo $array_keys[$key];

您应该在一次遍历数组中执行所有检查。
我的代码片段将提供第一个限定行的键（包含最低的[0]值，并且done值为no）。
代码：（Demo）

$graph = [
    "CityB" => ["0" => "1", "1" => "CityA", "done" => "no"],
    "CityA" => ["0" => "1", "1" => "CityC", "done" => "no"],
    "CityD" => ["0" => "1", "1" => "CityD", "done" => "yes"],
    "CityC" => ["0" => "5", "1" => "CityA", "done" => "no"]
];

$result = [];
foreach ($graph as $key => $row) {
    if ($row['done'] === 'no' && (!isset($result[$key]) || $row[0] < $result[$key])) {
        $result[$key] = $row[0];
    }
}

echo key($result) ?? 'No "done => no" rows';

输出：

CityB