Dijkstra algoritm coding on multileg itineraries

1 次查看（过去 30 天）
Davide Spano
Davide Spano 2021-11-27
编辑： Davide Spano 2021-11-29
Hi to everybody, I'm a fresh newby in this forum and actually to Matlab too.
I'm looking for a solution to a problem I heard would be resolvable with the Dijkstra algoritm, but I am not really sure if it would be the real solution.
My problem is the following:
  1. I got a list of 764 ocurrencies (Variables: Code, County_name, Lon, Lat);
  2. an another matrix with the distances between pairwise of 32 nodes
  3. The geodesic distance between pairwise of any singular origin/destination (764) and the nodes
I need to perform the calculation tha allow me to find the minimum distance between all the pairwise of the 764 ocurrencies passing by the two of the 32 nearest nodes
I'm working on it for a very lasting time, and also if I can conceptualise that in my mind, I'm looking to a good solution that could allow to me to manage all the new 500k+ and I think the Dijkstra algoritm would be a good solution, but I can't find right way to code it.
Hope someone could help, thanks

请先登录，再回答此问题。

采纳的回答

Yongjian Feng
Yongjian Feng 2021-11-27
Dijkstra algorithm actually gives you the seudo-code of the implementation. Just need to translate that seudo-code into matlab. What do you mean "the right way" then?
  3 个评论
显示 1更早的评论
Yongjian Feng
Yongjian Feng 2021-11-27
My understanding is that Dijkstra's algorithm doesn't need node values. The nodes need indices to identify them, but no values needed.
But I think Dijkstra's algorithm uses fixed source node. Or say it gives you only the shortest pathes between the selected source node and another node.
If you want any pair of nodes, you might need to look at Floyd's algorithm.
Davide Spano
Davide Spano 2021-11-29
编辑：Davide Spano 2021-11-29
Hi Yongjian!
I was having a look at Floyd's algorithm you suggested me on saturday, I think it also is not what I am looking for.
Think a moment about my problem in this way:
I got a matrix with 8 columns. The first two are the coordinates of the origin point (lon, lat), the second pair are the coordianate of the nearest train station, the third pair are those of the train station nearest tothe destination point, and the last pair are those of the destination point.
The occurrences are all the pairs of origin and destination points ((n*(n-1))/2)) with n=764 that I already have in an excel worksheet.
The aim of the challenge is to calculate the distance in the following way
Origin to Dep Station + Dep Stat to Arr Stat + Arr Stat to Dest.
with Dep Stat to Arr Stat = train line in Km (I have already calculate too for each pairs of train stations that are in number of 32)
when Dep Stat = Arr Stat then "train line"=1
Finally compare and chose the minimum between this multileg route and a geodesic distance.
I was thinking to write down the code as :
%define an optimal route to point Or to point Dst using a train leg
for each i in origin
leg1=geodist(origin, DepSt)
leg2= for each j in TrainStation
if Kj=Kj
then Kj+kj=1
else kj+kj="line lenght"
end
end
for each i in destination
leg3=geodist (ArrST,Destination)
end
multileg = leg1+leg2+leg3
end
%define a variable named optimalroute
optrt= min(geodist(o,d), multileg(o,d))
Now, I am aware that this sintax would never run, but this is an another way to try to define the problem with I am coping, but I am also aware I am really bad at coding.
Thanks, for any suggestion you cold give me.
D.

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Dijkstra algorithm 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by