File
simple_dijkstra.m
Name
simple_dijkstra
Synopsis
simple_dijkstra - Implements the Dijkstra algorithm and returns the distance from a single vertex to all others, but does not save the path.
Introduction
NOTE: PART OF A SET OF 8 RELATED FILES:
To investigate the dynamic propagation of systemic risk, the authors measure the direction of the relationship between institutions using Granger causality. Specifically, the authors analyze the pairwise Granger causalities between the t and t + 1 monthly returns of the 4 indexes; they say that X Granger-causes Y if c1 has a p-value of less than 5%; similarly, they say that Y Granger-causes X if the p-value of b1 is less than 5%. They adjust for autocorrelation and heteroskedasticity in computing the p-value.
License
=============================================================================
Copyright 2011, Dimitrios Bisias, Andrew W. Lo, and Stavros Valavanis
COPYRIGHT STATUS: This work was funded in whole or in part by the Office of
Financial Research under U.S. Government contract TOSOFR-11-C-0001, and is,
therefore, subject to the following license: The Government is granted for
itself and others acting on its behalf a paid-up, nonexclusive, irrevocable,
worldwide license to reproduce, prepare derivative works,
distribute copies to the public, perform and display the work.
All other rights are reserved by the copyright owner.
THIS SOFTWARE IS PROVIDED "AS IS". YOU ARE USING THIS SOFTWARE AT YOUR OWN RISK. ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS, CONTRIBUTORS, OR THE UNITED STATES GOVERNMENT BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
=============================================================================
Inputs
Outputs
Code
% Run warning message
warning('OFRwp0001:UntestedCode', ...
['This version of the source code is very preliminary, ' ...
'and has not been thoroughly tested. Users should not rely on ' ...
'these calculations.']);
num_nodes = size(A,1);
% Initialize all the distances to inf
distances = inf*ones(1,num_nodes); % distance s-all nodes
% Self-distance is 0
distances(node) = 0;
T = 1:num_nodes; % node set with shortest paths not found yet
while ~(isempty(T))
[d_min,index] = min(distances(T));
for j=1:length(T)
% If there is connection and current distance is closer, update it
if A(T(index),T(j))>0 && distances(T(j))>distances(T(index)) ...
+A(T(index),T(j))
distances(T(j))=distances(T(index))+A(T(index),T(j));
end
end
T = setdiff(T,T(index));
end
Examples
NOTE: Numbers used in the examples are arbitrary valid values.
They do not necessarily represent a realistic or plausible scenario.
Visual representation of the graph used:
N4
| \
N1 - N2 - N3 N6 <-- not connected
\ /
\ /
N5
Adjacency_matrix may be symmetric or non-symmetric as granger relationships can be unidirectional or bidirectional between nodes.
adjacency_matrix = [0,1,0,0,1,0; ...
1,0,1,1,0,0; ...
0,1,0,1,1,0; ...
0,1,1,0,0,0; ...
1,0,1,0,0,0; ...
0,0,0,0,0,0];
node = 1;
distances = simple_dijkstra(adjacency_matrix,node);
References