-
Notifications
You must be signed in to change notification settings - Fork 45
/
route_planner.m
65 lines (58 loc) · 1.89 KB
/
route_planner.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
function [route, dist] = route_planner(dg, S, T)
% find shortest path in graph of road intersections (nodes)
%
% usage
% [route, dist] = ROUTE_PLANNER(dg, S, T)
%
% input
% dg = directed graph of road network
% = [N x N] matrix
% (element i,j is non-zero when the connection between nodes
% i->j exists). Use the connectivity_matrix returned by function
% extract_connectivity.
% S = route source (start) node
% = node index (int)
% T = route target (destination) node
% = node index (int)
%
% output
% route = matrix of subsequent nodes traversed
% dist = total distance covered by route, counting as unit distance a
% transition between nodes (Remark: this is NOT the actual
% distance over the map for this route).
%
% dependency
% dijkstra, part of File Exchange ID = 24134,
% (c) 2008-2009 Stanford University, by David Gleich
% http://www.mathworks.com/matlabcentral/fileexchange/24134-gaimc-graph-algorithms-in-matlab-code
% OR
% graphshortestpath, part of MATLAB Bioinformatics Toolbox.
%
% 2010.11.17 (c) Ioannis Filippidis, jfilippidis@gmail.com
%
% See also EXTRACT_CONNECTIVITY, PLOT_ROUTE, PLOT_ROAD_NETWORK, PLOT_NODES.
%% find path
% BioInformatics Toolbox available ?
if exist('graphshortestpath', 'file')
[dist, route] = graphshortestpath(dg, S, T, 'Directed', true,...
'Method', 'Dijkstra');
else
[d, pred] = dijkstra(dg, S);
route = [];
curnode = T;
curpred = pred(curnode);
while curpred ~= 0
route = [curpred, route];
curnode = curpred;
curpred = pred(curnode);
end
dist = d(T);
end
% no path found ?
if isempty(route)
warning('No route found by the route planner. Try without road directions.')
return
end
%% report
disp('Distance: ')
disp(dist.')