-
Notifications
You must be signed in to change notification settings - Fork 29
/
kShortestPath.m
154 lines (142 loc) · 6.45 KB
/
kShortestPath.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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
function [shortestPaths, totalCosts] = kShortestPath(netCostMatrix, source, destination, k_paths)
% Function kShortestPath(netCostMatrix, source, destination, k_paths)
% returns the K first shortest paths (k_paths) from node source to node destination
% in the a network of N nodes represented by the NxN matrix netCostMatrix.
% It returns
% [shortestPaths]: the list of K shortest paths (in cell array 1 x K) and
% [totalCosts] : costs of the K shortest paths (in array 1 x K)
%==============================================================
% Meral Shirazipour
% This function is based on Yen's k-Shortest Path algorithm (1971)
% This function calls a slightly modified function dijkstra()
% by Xiaodong Wang 2004.
% * netCostMatrix must have positive weights/costs
%==============================================================
% DATE : December 9 decembre 2009
% Last Updated: April 2 2010
% Changes:
% 1-previous version(9/12/2009)did not handle some exceptions which should
% have returned empty matrices for the return values (added lines 20 and 29)
% 2-includes the changes proposed by Darren Rowland
%==============================================================
if source > size(netCostMatrix,1) || destination > size(netCostMatrix,1)
warning('The source or destination node are not part of netCostMatrix');
shortestPaths=[];
totalCosts=[];
else
%---------------------INITIALIZATION---------------------
k=1;
[path cost] = dijkstra(netCostMatrix, source, destination);
%P is a cell array that holds all the paths found so far:
if isempty(path)
shortestPaths=[];
totalCosts=[];
else
path_number = 1;
P{path_number,1} = path; P{path_number,2} = cost;
current_P = path_number;
%X is a cell array of a subset of P (used by Yen's algorithm below):
size_X=1;
X{size_X} = {path_number; path; cost};
%S path_number x 1
S(path_number) = path(1); %deviation vertex is the first node initially
%***********************
% K = 1 is the shortest path returned by dijkstra():
shortestPaths{k} = path ;
totalCosts(k) = cost;
%***********************
%--------------------------------------------------------
while (k < k_paths && size_X ~= 0 )
%remove P from X
for i=1:length(X)
if X{i}{1} == current_P
size_X = size_X - 1;
X(i) = [];%delete cell
break;
end
end
%---------------------------------------
P_ = P{current_P,1}; %P_ is current P, just to make is easier for the notations
%Find w in (P_,w) in set S, w was the dev vertex used to found P_
w = S(current_P);
for i = 1: length(P_)
if w == P_(i)
w_index_in_path = i;
end
end
for dev_vertex= w_index_in_path: length(P_) - 1 %dev_vertex is index in P_ of deviation vertex
temp_netCostMatrix = netCostMatrix;
%------
%Remove vertices in P before dev_vertex and there incident edges
for i = 1: dev_vertex-1
v = P_(i);
temp_netCostMatrix(v,:)=inf;
temp_netCostMatrix(:,v)=inf;
end
%------
%remove incident edge of v if v is in shortestPaths (K) U P_ with similar sub_path to P_....
index =1;
SP_sameSubPath={};
SP_sameSubPath{index}=P_;
for i = 1: length(shortestPaths)
if length(shortestPaths{i}) >= dev_vertex
if P_(1:dev_vertex) == shortestPaths{i}(1:dev_vertex)
index = index+1;
SP_sameSubPath{index}=shortestPaths{i};
end
end
end
v = P_(dev_vertex);
for j = 1: length(SP_sameSubPath)
for i = 1: length(SP_sameSubPath{j})
if SP_sameSubPath{j}(i) == v
next = SP_sameSubPath{j}(i+1);
temp_netCostMatrix(v,next)=inf;
end
end
end
%------
%get the cost of the sub path before deviation vertex v
sub_P = P_(1:dev_vertex);
cost_sub_P=0;
for i = 1: length(sub_P)-1
cost_sub_P = cost_sub_P + netCostMatrix(sub_P(i),sub_P(i+1));
end
%call dijkstra between deviation vertex to destination node
[dev_p c] = dijkstra(temp_netCostMatrix, P_(dev_vertex), destination);
if ~isempty(dev_p)
path_number = path_number + 1;
P{path_number,1} = [sub_P(1:end-1) dev_p] ; %concatenate sub path- to -vertex -to- destination
P{path_number,2} = cost_sub_P + c ;
S(path_number) = P_(dev_vertex);
size_X = size_X + 1;
X{size_X} = {path_number; P{path_number,1} ;P{path_number,2} };
else
%warning('k=%d, isempty(p)==true!\n',k);
end
end
%---------------------------------------
%Step necessary otherwise if k is bigger than number of possible paths
%the last results will get repeated !
if size_X > 0
shortestXCost= X{1}{3}; %cost of path
shortestX= X{1}{1}; %ref number of path
for i = 2 : size_X
if X{i}{3} < shortestXCost
shortestX= X{i}{1};
shortestXCost= X{i}{3};
end
end
current_P = shortestX;
%******
k = k+1;
shortestPaths{k} = P{current_P,1};
totalCosts(k) = P{current_P,2};
%******
else
k = k+1;
end
end
end
end
%--------------------------------------------------------