Dijkstra algoritm coding on multileg itineraries

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

Answer 1

[Yongjian Feng]

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?

[Davide Spano]

Hi!

Thanks for your interest.

Well, upon what I seen until now Dijkstra algoritm would compute the shortest multileg itinerary upon nodes values and the weight of their linkage.

For now I don't know the nodes values (unless I assume them as =1 ) but just the linkage weight (distances). In that my needs are quite different.

I need to calculate all the itineraries linking points i, j using intermediate nodes k (for that, if I have two points that use the same node, then the itinerary would be i-k-k-j being k-k=1)

In a second step I need to compare the lenght of one of the previous itineraries with a geodesic distance between pairwise i,j (that I have already calculate) and chose the shortest.

Hoping to have better explained the issue.

[Yongjian Feng]

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]

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.