19 Replies Latest reply: Jun 9, 2016 9:41 AM by Stefan Wühl

# Finding the shortest route between two paths

Hi Guys,

I have a table that is having the train information like train no , train name, source station name, destination station name, distance

the table looks like this:

Train No    Train Name       Source Station Name      Destination Name    Distance

--------------------------------------------------------------------------------------------------------------

1               ABC                           A                                   B                         10

2               CDE                           B                                   E                         30

3              EFG                            E                                   D                         40

4               HIJ                             E                                   F                         20

5               KLM                           B                                   D                         10

what I need is if I select Source Station : A and Destination : D then it should give the me list of all the train numbers, I need to connect to reach to the destination using shortest distance .

For example: from  A To D : A->B->D = 20 then the train no will be 1,5

2:    A->B->E->D= 80 then the train numbers will be 1,2,3

This is what I need , it would be great if anyone can help me finding the solution

Thanks,

Vivek

• ###### Re: Finding the shortest route between two paths

Since this calculation involves a recursive calc I don´t think this can be done using regular QlikView expressions. Maybe using a macro (not sure about this)

Dijkstra's algorithm - Wikipedia, the free encyclopedia

• ###### Re: Finding the shortest route between two paths

Maybe you can create a solution using a script that creates hierarchy tables.

• ###### Re: Finding the shortest route between two paths

Hi Swuehl,

Can you give me the expressions that you have used , so that i will try

Thank you,

Vivek

• ###### Re: Finding the shortest route between two paths

Attached is the script code.

I then created the two list boxes for SourceSelect and DestinationSelect and a straight table:

=Aggr(If(Left(Path,1) = SourceSelect and Right(Path,1) = DestinationSelect, Path),Path) sum({<AncestorName = {"*"}>}Distance) Concat(AncestorName,',')
A/B/D201,5
A/B/E/D801,2,3

That's just an outline of a possible solution (not even sure if this will work for more complex scenarios).

• ###### Re: Finding the shortest route between two paths

Hi Swuehl,

In the script u have loaded concatenated the following

CONCATENATE

LOAD Null() as [Source Station Name],[Source Station Name] as [Destination Name]

RESIDENT  Trains;

Why do we need to do that, if not what will happen can you explain me

Thanks,

Vivek

• ###### Re: Finding the shortest route between two paths

In a hierarchy LOAD, the root nodes should be loaded with parent node being NULL.

Not sure if we need this here, if you want to know what happens if you remove this part, just try it.

edit: I think if you remove the concatenated records, the HIERARCHY LOAD  prefix will not work correctly.

From the HELP:

All nodes with a parent id not found in the node id column (including nodes with missing parent id) will be considered as roots. Also, only nodes with a connection to a root node - direct or indirect - will be loaded, thus avoiding circular references.

• ###### Re: Finding the shortest route between two paths

Hi Swuehl,

If a person want to go from B to A , if he selects B in source and A in destination is it possible and if I have a record which shows the information of the train that travels from B to A. In that case what should I do

Thanks

Vivek

• ###### Re: Finding the shortest route between two paths

It should be possible if your source data actually contains possible routes for that combination of Source and Destination. Currently, in your sample records, it doesn't, right?

• ###### Re: Finding the shortest route between two paths

Hi Swuehl,

I tried it by inserting a record but it does not works, should I need to change any thing else.

Thank You,

Vivek

• ###### Re: Finding the shortest route between two paths

The HIERARCHY LOAD prefix might be limited to routes without possible loops, which I think is hard to ensure.

I've tried to create a similar approach without using the HIERARCHY LOAD prefix, but using a loop that iteratively joins all source stations to the previous destination stations.

=Aggr(If(Left(Path,1) = SourceSelect and Right(Path,1) = DestinationSelect, Path),Path) TotalDistance Path
A/B/D20A/B/D
A/B/E/D80A/B/E/D

edit:

Also attaching a slightly modified version where the selection of source and destination station is linked to the path.

• ###### Re: Finding the shortest route between two paths

Hi Swuehl,

When I am connecting it with my data it is taking too much of time and get stuck in the middle, I don't have any clue can you help me out

Thank You,

Vivek

• ###### Re: Finding the shortest route between two paths

How many stations / connections do you have in your data?

Can you estimate the max number of stations on any given route?

• ###### Re: Finding the shortest route between two paths

Hi Swuehl,

What should I do now?, No I can't estimate maximum number of stations for any given route.

Thank you,

Vivek

• ###### Re: Finding the shortest route between two paths

Hi Swuehl,

I am having 356 source and 356 destinations , in that case they are connected in the one or the other way I feel

what should I do now?

Thanks,

Vivek

• ###### Re: Finding the shortest route between two paths

For i = 1 to FieldValueCount('Destination Name')-1

use a low upper limit, like

For i = 1 to 2

then investigate in the SourceSelect and DestinationSelect, if all possible combinations are possible.

This might not find the optimal path, though.

If you get a feeling for the number of possible routes created, slowly increase the upper limit of the for loop.

It will depend on the properties of your network how much iterations you will need to find all connections and a at least near-optimal route.

Note that this approach is a brute force one, if you need to handle thousands of stations with a lot of possible destinations, this brute force approach will not work (well).

There are specialized tools for route optimization and you might want to have a look into some other external tools as well.

• ###### Re: Finding the shortest route between two paths

Hi Swuehl,

I have attached an image in this if I select B as source and E as destination then it give me two train nos :1,2  but ideally it should be 2 I feel , then how can I remove it?.

Sorry for troubling you.

Thanks,

Vivek

• ###### Re: Finding the shortest route between two paths

I don't support version 0.9 anymore

• ###### Re: Finding the shortest route between two paths

Hi Swuehl,

I am Using Version 11 , Is it because of that ??

Thank you,

Vivek

• ###### Re: Finding the shortest route between two paths

No, sorry, I am referring to my latest uploaded QVW sample file.

This should not show the two train numbers when you are expecting only one.

The field is called TrainSeq