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
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 CenterFile Exchange에서 Dijkstra algorithm에 대해 자세히 알아보기

Community Treasure Hunt

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

Start Hunting!

Translated by