PHP 解决最短路径问题

WechatIMG59.jpeg

最短路径问题

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

图解

矩阵最小路径问题-左上右下(1).gif

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<?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);

执行

1
2
$ php minPath.php
最短路径:17

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

-------------本文结束感谢您的阅读-------------
0%