image thumbnail

Code for Djikstra's Algorithm

version 1.0.0.0 (1.16 KB) by Anwaya rath
This code successfully finds out the shortest path between source node and destination node.

109 Downloads

Updated 18 May 2017

View License

The above code is used to find the minimum distance between the Source node (A) to all the given nodes, and as well as a particular destination node for non-negative edge weights via the Djikstra’s Algorithm. where the matrix m is composed of the source nodes, matrix n consists of the destination nodes, and w represents the corresponding weights of the edges connecting the source and destination.
The basic syntaxes which are used are as follows:
1. S= Sparse(m,n,w): It generates a sparse matrix from triplets m, n and w such that S(m(k),n(k))=w(k). Here, the matrix m represents the list of source nodes in the network, and the matrix represents the destination nodes, and matrix w represents the corresponding edge weights.
2. A=full(S): It converts a sparse matrix S into a full storage organization i.e, it generates a full matrix of the given sparse matrix, with non zero matrix values specified as edge weights, whose indices(of the non zero values) are given by (m,n).
3. G=digraph(m,n,w,): Creates a directed graph G of all the source nodes in m to all destination nodes n, and it also specifies the edge weights from the array of weights w.
4. Initialize the minimum distance of all the nodes except source node to infinity, and distance of the source node as 0. All distances are to be measured from source node. This is done using the distance() variable. The source node is designated by s.
5. We also initialize the parent node of every node in the network to zero, as done by the variable predecessor().
6. In this case, we have to maintain a heap of all those nodes which are removed as we continue updating the distance from the source node on every iteration. This is done by the variable visited() .
7. During the iteration, we may have to store the temporary distances calculated into a variable. The matrix temp can be used to store such values.
8. After we have calculated the distance of all nodes from the source node, by incorporating the theory of relaxation, we now consider a matrix M which gives us the indices of the shortest path (it specifies the nodes) from the source node to a desired destination node as specified by the user. TotalCost is a variable which is used to store the value of the total distance of the source node to the specified destination node.
9. Shortestpath(G,s,d): Calculates the shortest path from source node s to specified destination node d in the directed graph G.
10. highlight(p, TR, ’Color’,’g’): highlights a subset of nodes included in the shortest path TR by changing their color to green.

Cite As

Anwaya rath (2022). Code for Djikstra's Algorithm (https://www.mathworks.com/matlabcentral/fileexchange/63005-code-for-djikstra-s-algorithm), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2016b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Tags Add Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!