php初心者, 记录自己工作和学习路上的感想和笔记

0%

dijkstra算法 PHP 实现

20171119 利用周末优化了一下代码。这次完全默写了出来。感觉好多了

这个是根据算法图解自己写的,理解的不是很好,注释都在代码里面,过几天再默写一下,好好理解一下

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
<?php

// 构造图
$graphs = [];
$graphs['start'] = [];
$graphs['start']['a'] = 5;
$graphs['start']['b'] = 2;

$graphs['a'] = [];
$graphs['a']['c'] = 4;
$graphs['a']['d'] = 2;

$graphs['b'] = [];
$graphs['b']['a'] = 8;
$graphs['b']['d'] = 7;

$graphs['c'] = [];
$graphs['c']['d'] = 6;
$graphs['c']['fin'] = 3;

$graphs['d'] = [];
$graphs['d']['fin'] = 1;

$graphs['fin'] = [];

// 处理过的节点
$processed = [];
// 所有节点的消费
$costs = [];
// 所有节点的父节点
$parents = [];

function getNodeCost($graphs, $nodeName = 'start', $isStartNode = false)
{
if (empty($graphs)) {
return [];
}
$costs = [];
foreach ($graphs[$nodeName] as $name => $length) {
if ($isStartNode) {
$costs[$name] = $length;
} else {
$costs[$name] = INF;
}
$costs += getNodeCost($graphs, $name);
}

return $costs;
}

$costs = getNodeCost($graphs, 'start', true);

function getNodeParents($graphs, $nodeName = 'start', $isStartNode = false)
{
if (empty($graphs)) {
return [];
}
$parents = [];
foreach ($graphs[$nodeName] as $name => $length) {
if ($isStartNode) {
$parents[$name] = $nodeName;
} else {
$parents[$name] = null;
}
$parents += getNodeParents($graphs, $name);
}

return $parents;
}

$parents = getNodeParents($graphs, 'start', true);

function findLowestCostNode($costs, $processed)
{
$lowestNodeLength = INF;
$lowestNOdeName = '';
foreach ($costs as $name => $length) {
if ($length < $lowestNodeLength && !in_array($name, $processed)) {
$lowestNodeLength = $length;
$lowestNOdeName = $name;
}
}

return $lowestNOdeName;
}

$nodeName = findLowestCostNode($costs, $processed);
while ($nodeName) {
$currentNodeCost = $costs[$nodeName];
foreach ($graphs[$nodeName] as $name => $length) {
if ($currentNodeCost + $length < $costs[$name]) {
$costs[$name] = $currentNodeCost + $length;
$parents[$name] = $nodeName;
}
}
$processed[] = $nodeName;
$nodeName = findLowestCostNode($costs, $processed);
}

var_dump($costs);
var_dump($parents);