No License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
dijkstra very simple

4.1 | 7 ratings Rate this file 60 Downloads (last 30 days) File Size: 1.62 KB File ID: #14661 Version: 1.0

dijkstra very simple


Jorge Barrera (view profile)


14 Apr 2007 (Updated )

Dijkstra's algorithm to find the shortest path

| Watch this File

File Information

This is an implementation of the Dijkstra´s algorithm, which finds the minimal cost path between two nodes. It´s supposed to solve the problem on positive weighted instances.


Dijkstra Shortest Path Routing inspired this file.

This file inspired Dijkstra Lowest Cost For Images, Modified Dijsktra's Algorithm To Return All Paths That Tie For Shortest, and A Solution To The Maze Problem With Dijkstra.

MATLAB release MATLAB 7.1.0 (R14SP3)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (17)
30 Dec 2016 mimine

mimine (view profile)

i understood the programme but it didn't work forme and i don't know why so can you help me please

Comment only
20 Apr 2016 lightningakashakash

best code. thanks. :)

06 Apr 2015 mina

mina (view profile)

hi. i want to make a WSN and implement one of the intelligent routing protocols on it.for start i dont know how to simulate a WSN. would anyone help me or send me anything helpful?
thank you

Comment only
08 Jul 2014 Bas

Bas (view profile)

I think you could speed up Dirk Stelder's solution by replacing the first for loop (between "candidate=[];' and "[u_index u]=min(candidate);") by the statement

[u_index u] = min(1 ./ (S==0) .* dist);

(Note that u_index is in fact the value; u is the index.) Entries in 1 ./ (S==0) have value Inf when their value in S is 1, i.e. when they have been visited, and 1 otherwise. Multiplying by dist leaves all visited nodes with distance Inf: precisely what 'candidate' looks like.

Comment only
12 Sep 2013 Dirk Stelder

here is a simple rewrite that runs well for large networks. Th costmatrix is sparse (no entries for non-existing links) and only total costs are calculated:

function [spcost] = dijkstra(costmatrix, s, d)

% uses sparse matrix and ingores paths to save time and memory for large networks
% calculates totals cost only

% This is an implementation of the dijkstra´s algorithm, wich finds the
% minimal cost path between two nodes. It´s supoussed to solve the problem on
% possitive weighted instances.

% inputs:
% n*n costmatrix, can be sparse for nonexisting links
% n: the number of nodes in the network;
% s: source node index;
% d: destination node index;

%For information about this algorithm visit:

%This implementatios is inspired by the Xiaodong Wang's implememtation of
%the dijkstra's algorithm, available at
%file ID 5550

%Author: Jorge Ignacio Barrera Alviar. April/2007
%Edited Dirk Stelder September/2013

S(1:n) = 0; % vector, set of visited vectors
dist(1:n) = inf; % it stores the shortest distance between the source node and any other node;
prev(1:n) = n+1; % Previous node, informs about the best previous node known to reach each network node

dist(s) = 0;

while sum(S)~=n
for i=1:n
if S(i)==0
candidate=[candidate dist(i)];
candidate=[candidate inf];
[u_index u]=min(candidate);
for i=1:n
if costmatrix(u,i)>0 % ignore non-existing links (=zero in sparse matrices) to save time and memory
spcost = dist(d);

Comment only
24 Apr 2013 Barsam

Barsam (view profile)

Really helped me, thanks!

29 Mar 2013 Damdamdam


08 Apr 2012 David B

David B (view profile)

This is great code. As others have pointed out, it could be commented better, but having said that, it's the easiest implementation of Dijkstra's Algorithm to understand that is available on the file exchange. As a beginner programmer, I appreciate the simplicity.

The previous commenter pointed out, matriz-costo is an n x n adjacency matrix. To elaborate, elements reflect the cost of traveling between corresponding nodes. Any element set to zero implies a cost-free path exists between those two nodes. I usually set the elements corresponding to non-adjacent nodes to an arbitrarily large number (it might also work to set them to inf -- I haven't tried it).

My one wish is that the output included multiple paths if there is a tie for which path is shortest. I modified the code to return ties. It is posted here:

Thank you!!

01 Mar 2012 Frederick

For the people who look for input:
matriz_costo is the adjacency matrix (n by n matrix with distance or cost from one point/node to another
s is startnode
d is endnode

Comment only
02 Dec 2011 Chua

Chua (view profile)


Comment only
03 Oct 2011 Yannos M

script should be removed! One of the worst documentations ever..and very bad English.what is the size of s,d, matriz_costo???

02 Mar 2011 cynthia

matriz_costo means?

Comment only
06 Dec 2010 Petr Dostal

Any information about the inputs and outputs of dijkstra's algorithm. Can you present an example? Thanks!

Comment only
28 Jul 2008 li li

need it to research

Comment only
24 Jul 2008 Dominik Kaspar

A convenient implementation of Dijkstra's Shortest Paths algorithm.

29 Dec 2007 Dimitri Strobbe

I loved this! Not too much information about the algorithm itself (dijkstra), but very nice and helpfull for my thesis!

29 Dec 2007 Dimitri Strobbe

I loved this! Not too much information about the algorithm itself (dijkstra), but very nice and helpfull for my thesis!

Comment only

Contact us