PHP 解决最短路径问题

最短路径问题

wiki:最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

图解

代码

<?php 
function minPath($matrix) {
	$row = count($matrix);
	$col = count($matrix[0]);
	if ($row==0 || $col==0) {
		return 0;
	}
	$dp = array_fill(0, $row, array_fill(0, $col, 0));
	$dp[0][0] = $matrix[0][0];

	for ($i=1; $i < $row; $i++) { 
		$dp[$i][0] = $dp[$i-1][0]+$matrix[$i][0];
	}

	for ($j=1; $j < $col; $j++) { 
		$dp[0][$j] = $dp[0][$j-1]+$matrix[0][$j];
	}

	for ($i=1; $i < $row; $i++) { 
		for ($j=1; $j < $col; $j++) { 
			$dp[$i][$j] = min($dp[$i-1][$j], $dp[$i][$j-1])+$matrix[$i][$j];
		}
	}

	return $dp[$row-1][$col-1];
}
$matrix = [
	[2,5,3,5],
	[7,1,3,4],
	[4,2,1,6],
];
echo "最短路径：".minPath($matrix);

执行

$ php minPath.php
最短路径：17

关联

[[Java 解决最短路径问题]]
[[Go 解决最短路径问题]]