version 1.0.0.0 (3.43 KB) by
Joseph Kirk

calculates the shortest path and distance between two nodes on a map

This function can

1. Find the shortest path and distance from a starting node to an ending node on a map**

2. Find the shortest paths and distances from a starting node to ALL other nodes on a map**

**The map should consist of nodes and segments, such that:

1. nodes have the format [ID X Y] or [ID X Y Z] (with ID being an integer, and X,Y,Z representing position coordinates and of type double)

2. segments have the format [ID N1 N2] (with ID being an integer, and N1 N2 representing IDs from the nodes list such that there is an [undirected] edge/segment between node N1 and node N2, and obviously of integer type also)

Note:

The function generates a random map of nodes and segments that it uses if no inputs are given. This way, it acts like a script if it is run with no inputs, and it acts like a function otherwise.

Joseph Kirk (2021). Dijkstra's Shortest Path Algorithm (https://www.mathworks.com/matlabcentral/fileexchange/12850-dijkstra-s-shortest-path-algorithm), MATLAB Central File Exchange. Retrieved .

Created with
R2006b

Compatible with any release

**Inspired by:**
Dijkstra Shortest Path Routing

**Inspired:**
Dijkstra's Minimum Cost Path Algorithm

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

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

navanit dubeyhttps://in.mathworks.com/matlabcentral/answers/650538-how-to-find-kshortest-path-or-use-dijkstra-algorithm-for-12-plot-points?s_tid=prof_contriblnk

how should i do this plz help

长方 姬great!

Javier Belmontesibabalo noludwweHi Joseph

Undefined function or variable 'dijkstra'.

how do i define Dijkstra in my code

iqra aslamhellow sir would u tell how to run .... it does not show path

Eric ChadwickThis is great! Can you point me to a Citation of Dijkstra’s algorithm and/or a way to cite your code?

Antonio SmithHi Joseph,

I can plot a 3D graph now but I want to know what is the maximum input nodes in this program?

Thank you very much.

Antonio SmithHi Joseph,

After I try your function by inputting 2D nodes, I try to input 3D nodes. However, I don't know how to plot a 3D-graph after I input 3D nodes.

Could you please give me an example of inputting 3D nodes?

Thank you very much!

Antonio

Masato KoizumiHello Joseph,

Dear Joseph,

I was curious if there is a way to calculate not the shortest distance but the second shortest distance using your Dijkstra's Shortest Path Algorithm.

Thank you.

Masato Koizumi

songming heAntoine QUINQUENELJoseph Kirk@indu, you may wish to try this version:

http://www.mathworks.com/matlabcentral/fileexchange/20025

Then try the following:

C = netCost;

[costs,paths] = dijkstra(logical(C),C,[11 12 14],1)

indui have 14 nodes in my network and i have to find shortest distance from node 11,12,14 to the destination node 1.

Nodes =[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

source nodes =[11,12,14]

destination node =[1]

input=netCost Matrix [15x15]

how can i find shortest path and their corresponding total cost using matlab?

How can i solve thsia

chris wuchris wuFayez TalmeesThank You Joseph Kirk

Joseph Kirk@Andrea, you may wish to try this version:

http://www.mathworks.com/matlabcentral/fileexchange/20025-dijkstra-s-minimum-cost-path-algorithm

Andreacan this be generalized to the directed case?

taurusong songAnaleze EricaRick HillThank you for your algorithm, it has been very helpful. Do you know the complexity (big O notation) of your algorithm?

Rick Hillhglgreat work!!

Hatim SalihGreat work.

mel Samiai think this program is really good.

rajat soniRonan@Joseph Kirk I looked at other examples that auto connected links to every node but now Iv realised I actually needed to manually specify the segments, so your solution is much preferred. I got it working the way I wanted. Thank you very much.

Joseph Kirk@Ronan, there is a way, yes, but without knowing the specifics of your problem it is difficult to guess where you are having issues.

However, you might try using this version of Dijkstra's Algorithm first to see if it is more intuitive:

http://www.mathworks.com/matlabcentral/fileexchange/20025

By the way, I am not sure why you say you have to generate the segments manually - because the whole point of Dijkstra's algorithm is to find shortest paths in a graph, which (by definition) consists of nodes/vertices and segments/edges - so if you do not already have nodes and segments defined, it is unclear why you are trying to use this function at all.

Ronanis there an example for getting the shortest paths from starting node to ALL other nodes? I was able to run the example included in the script but it seems that I have to generate the segments manually.

Vishal GirisagarHi,

I need to use this. I am getting confused with the input form that should be given.

For ex:

I have 4 simple nodes.

1 2 3 4

1->2: weight = 10

1->3: weight = 20

2->4: weight = 30

3->4: weight = 40

i need to find path from 1 to 4.

Can you tell me how to give input.

PuffeltjeI have a database with nodes en segments but the segments must be calculated before they can be added to the algorithm. I have a query wich calculates all the posible segments from one specific node to other nodes.

Is it possible to calculate the needed segments during the algorithm? In that case i don't have to calculate all the possible segments for the whole database (16,000 nodes with about 2,450,000 segments)

Puffeltje

SunilHi All,

I have a need, wherein there are multiple nodes spread across. All I know is the location of each nodes. How do I find the best path from all nodes to a particular node?

Can I use the "Dijkstra's Shortest Path Algorithm"? Believe, its YES.

I am not sure, as how do I populate the variable, “segments” in program.

Appreciate an earlier response on this. Would be great, if you could give a code snippet as well.

Thanks

Sunil Kumar

Joseph Kirk@Tyler, my other version can:

http://www.mathworks.com/matlabcentral/fileexchange/20025-advanced-dijkstras-minimum-path-algorithm

TylerCan this program find the shortest path from a distance matrix?

Surender moodei will not understand this please explain me

AndreaJesus LuevanoHi, when I try to use the algorithm to optimization route, always it asks me the segments from the nodes, what happens if I do not know them, because I trying to get the optmization route of an image.

by the way, I do not understand the CMatrix relationship with the real image on the biograph function.

Xilu WangBenjamin KnightGreat code, well documented and easy to apply. Note that I needed to transpose A and C matrices to get a result from this function.

abdullah rfdgsdfPerfect >> thank u man ... go head

Michael AshbyVery useful code for finding the distances from a given node to all the others.

Thanks to the author for assistance and updates.

Weihao YinKuba Wuioannis tsolakidisCharles KingstonThis already exist in one of the matlab demos.

Nikhil MVery Good; Thanks;

The AuthorChuthamart - If you're going to give a rating of 1, an explanation would be nice...

Chuthamart PanklinOmer KAMALcan u make it for 7 nodes to see the output.

Bandi Reddyhan dazaworks like a charm!! quite fast, in my case 342 nodes (708 segments) ~ 0.3 secs. it even works if the nodes you feed in are not all used by the segments !! thanks

titin siburiani think this program is really good.

Daren O'ConnorGreat! Fast, efficient, and easy to use.