-
Notifications
You must be signed in to change notification settings - Fork 1
/
bellmanFord.m
107 lines (102 loc) · 3.02 KB
/
bellmanFord.m
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
102
103
104
105
106
107
function [myTime, myPath, pathLeng] = bellmanFord(myNet, s, t, k)
%% This function searchs the first k-shortest paths using
% multi-label version of Bellman-Ford algorithm.
% input: myNet, a sctruct contains the road network
% s, the starting node of the paths
% t, the terminating node of the paths
% k, the number of shortest paths
% output: myTime, the travel time of all the paths
% myPath, a struct contains the k-shortest path
% pathLeng, the length of paths
%
% Yiliang Xiong <[email protected]>
% Sat Dec 11 21:44:42 2010 +0800
%% define variables
% the quickest travel times
quickTime = Inf(myNet.numNode, k);
% the list of preceding nodes
preNode = -ones(myNet.numNode, k);
% the list of preceding labels
preLabel = -ones(myNet.numNode, k);
%% a queue for searching: first field -- node, second field -- label
sizeQueue = myNet.numLink;
queue = -ones(sizeQueue, 2);
% top of the queue
top = 0;
% bottom of the queue
bottom = 0;
% length of the queue
leng = 0;
% push method
function push(node, label)
leng = leng + 1;
bottom = mod(bottom, sizeQueue + 1) + 1;
queue(bottom, 1) = node;
queue(bottom, 2) = label;
end
% pop method
function [node, label] = pop()
if leng < 1
error('queue:pop', 'Cannot pop an empty quque. ')
else
leng = leng - 1;
end
top = mod(top, sizeQueue + 1) + 1;
node = queue(top, 1);
label = queue(top, 2);
end
%% Bellman-Ford algorithm
% initialize the travel time for starting node
quickTime(s, 1) = 0;
% push the starting node into the queue
push(s, 1);
while leng > 0
[node, label] = pop();
for i = 1:myNet.numAdjNode(node)
nextNode = myNet.adjNode(node, i);
travelTime = myNet.linkTime(node, i);
% linear time search (to be replaced in future)
[maxTime, itsLabel] = max(quickTime(nextNode, :));
if quickTime(node, label) + travelTime < maxTime
quickTime(nextNode, itsLabel) = quickTime(node, label) + travelTime;
preNode(nextNode, itsLabel) = node;
preLabel(nextNode, itsLabel) = label;
push(nextNode, itsLabel);
end
end
end
%% construct all the shortest paths
% sort the paths
quickTimeTab = [quickTime(t, :); ...
preNode(t, :); ...
preLabel(t, :)];
[sortedTab, sortedIndex] = sortrows(transpose(quickTimeTab), 1);
% cut out the paths with infinite travel time (actually it does NOT exist)
finiteTab = sortedTab(sortedTab(:,1)<Inf, :);
% sometimes the number of paths between (s,t) is smaller than k
kk = size(finiteTab, 1);
% throw a warning if kk < k
if kk < k
warning('bellmanFord:constructPaths', ...
'The number of paths between (%d,%d) is %d, smaller than %d! ', ...
s, t, kk, k);
end
% the quickest travel times
myTime = finiteTab(:, 1);
% list of all the shortest paths
myPath = -ones(kk, myNet.numNode);
pathLeng = zeros(kk, 1);
for i = 1:kk
iNode = t;
iLabel = sortedIndex(i);
while iNode > 0 && iLabel > 0
pathLeng(i) = pathLeng(i) + 1;
myPath(i, pathLeng(i)) = iNode;
nextNode = preNode(iNode, iLabel);
nextLabel = preLabel(iNode, iLabel);
iNode = nextNode;
iLabel = nextLabel;
end
end
% end of main function
end