Search
Search

## Introduction

What is Shortest Path Problem?
In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized.

There are some important points that we had to note when we try to solve such similar problems in XI.

1. Feeding the input with XML
2. Try to loop back to XI itself for recursive like functions.
3. Usage of BPM
4. Message Mapping – Java functions will be handy in transforming data while the XML is in recursive loop.

## Structuring the Input

The input is obviously XML. We can have two sections like running value tags and unchanged value tags. Hence the value changes from one mapping to another in temporary value tags and the values do not change in permanent value tags. So, why are these temporary and permanent value tags for? Well, in permanent section of the XML, we have the distances between all the cities and in the running section we have the distance from the question – source to all the other cities.

Assume we want to calculate distance from A to D
Running value tags:
(All routes and distances from city A)
A to B
A to C
A to D

Permanent value tags:
(All the cities and the available routes and distances
between them)
A to B
B to D
D to C
A to C

### How is the above structure help XI in solving the Shortest Path problem?

The basic initial idea is to use the same structure for input as well as output. Secondly, the same logic can be applied on the produced XML for different source cities updating the actually required distance. Finally, it is easier to lookup within the same XML structure rather than having the data in database or an external file.

The Logic:

Every city broadcasts its information to its neighboring cities. These neighboring cities will in turn update this information with respect to its neighbors and broadcasts it to its neighbors. This includes the source city also. The source city sends back (a broadcast message) if and only if there is any change. Through this the distance between the source and target can be easily found using XI by sweeping through the entire city network once.

## Theoretical Implementation

The above is a diagram representing the cities A-I with distance. Here we will use XI to find the shortest distance between A and I.

Let’s take the message from city A:
(Message Sent)

AB=3
AE=2
AG=3

Let’s take the message from city B:
(Before transforming)

BA=3
BF=3
BH=1

(After transforming)

AB=3
AF=6 (AB+BF), If ‘AF’ already exists, place the value which is smaller.
AH=4 (AB+BH)

(Message Sent)

AB=3
AE=2
AG=3
AF=6
AH=4

By doing this to all the cities we finally get a message with values all shortest distances from A to all cities.

## How to implement it on XI?

Every city can be considered as an interface mapping in XI with message from one city goes to another in the form of XML through BPM. A set of interface mappings and sequential transformations with all the cities (mappings) for no of cities, ‘n’- times the XML with the shortest distances from the required source will be produced

Algorithm for message mapping lookup: While updating the running value tags, a lookup is made on the permanent value tags for the distance between a particular source and destination. This value will get updated by adding the value of source to source tag, to make value from A (source) to destinations and comparing with the existing value to update the smaller value. Through this technique, the distance for intermediate cities are calculated and dynamically updated on the same XML and fed into the next city (interface maping) The real challenge lies in the Message mapping – java functions to do a lookup within the same XML and do arithmetic operations and update the same.

On the A practical implementation of Shortest Path Problem in XI  (Part II) of this blog series, we will look into the practical implementation of this shortest path problem.

To report this post you need to login first.

You must be Logged on to comment or reply to a post.

1. Former Member Post author
Interesting again!!

Yes…I am always there for your interesting blogs.:-)

My 1st Question is are you showing that how any
XYZ algorithm which can be done in java or other
platform can be done in XI (using
either msg mapping functions or module processors
or external libs in JAVA)? OR are you showing
how XI can be marketed to those companies
that are implementing this algo. for TSP?

services is going to setup 4 branches in Indian
Chennai and in each city they will be having
15-20 sub-branches.
All items that are couriered to a city reaches
to main branch first and then they are sent to
their sub-branches and finally to destination from sub-branch.

Now finding out the most feasible route from
main branch to sub-branches will be done say using TSP.
But it’s required only once as this is fixed.
Only variables will be from sub-brances to destinations
as they will vary daily.Now ABC courier services can obviously
develop an application which will cater to TSP problem,
Where we can give the distance input and total destinations
to be covered to get the feasible path. say as per your blog
these are all XML files,Then the application will take care
of extracting distance inputs from XMLs.

Now my Question here would be…How I (say manger
of IT dept. for ABC courier services) would be
for above problem?and how the ROI is promised?

Now coming to technical analysis as how TSP will work with XI,
then the 1st thing obviosly to consider is the number of
loops to XI when the number of destinations grow to
an extent.
Also…
>>The real challenge lies in the Message mapping –
>>java functions to do a lookup within the same XML
>>and do arithmetic operations and update the same.

Yes…
Many other factors go without saying like decreased
performance (even if BPM not used), increased maintenance.

Now if the aim of your blog was to show how any algo.
can be technically implemented using XI, then I may not be surprised
if you come up with say Leaky Bucket or Token bucket
algorithms or socket programming,or other routing algorithms,
computer networks in XI instead of java/c++.

Lastly, As u pointed out the logic:

>>Every city broadcasts its information to its neighboring cities. These neighboring cities will in turn update this information with respect

>>to its neighbors and broadcasts it to its neighbors. This includes the source city also. The source city sends back (a broadcast message)

>>if and only if there is any change. Through this the distance between the source and target can be easily found using XI by sweeping

>>through the entire city network once.

There is a major flaw in the above logic.What you have mentioned
in the statement for broadcasting of info is not Travelling Salesman Problem(TSP)
but it’s Minimal Spanning Tree(MST) problem.Because TSP doesn’t broad cast info
but only determines SHORTEST path connecting all
nodes.Ex: for TSP is like the courier service.
The MST broadcasts info in an OPTIMAL path for Ex: IRC (Internet Relay Chat), where
the nodes are servers that send the messages to other servers.

In the TSP one has to return to starting point after covering all locations.
But in broadcasting info (MST) the job is finihed once the last
The minimal spanning tree problem is a normal one.
But in TSP when ‘N’ (number of nodes)
tends to a very large number the solution cannot be guaranteed as
optimal (NP-complete problem) and in fact the research is still going on this TSP prob.

Anyways my point is…here it fails to give a true business motive
for above blog (if any).

Cheers
Sudhir

(0)
1. Former Member Post author
Hi,
Well..in the above comment I mentioned about TSP being NP-complete problem.I feel i should describe
a liitle what NP Problems are so if anyone is reading this he/she is not confused ๐

‘P’ problems are Class of decision problems that can be solved in
polynomial time (quick time)

NP(nondeterministic polynomial) problems are Class of decision problems
such that if the answer to the problem is yes, then there is a method
that can be checked/verified in polynomial time to show that the answer is
correct.
NP problems are one in which the “running time to find the solution” is
NOT ploymimial and that we have no way to prove that the ALGORITHM
we have to obtain the solution is the best.

The hardest problems in NP class are called NP-Complete and they have
a property that any problem in that class could be reduced to another.

Cheers
Sudhir

(0)
1. Sudhir,

It was on the technical part that was concentrated more rather than the

application. Whether TSP or MST, the core idea is to show how to solve such problems in XI.

I started off with TSP in my mind and while developing in XI, seeing the technical complexities, I first decided to find only the shortest distance and also avoided the back trip which happened to be Minimum Spanning tree.

When I was totally involved in developing this, I completely forgot that, the reduced version of Traveling salesman problem is nothing but Minimum spanning tree.

Anyway, I had completely updated my blog and also posted the technical part (Part – 2) of it. Once again, thank you for your valuable comment!!

Regards,
Felix

(0)
1. Former Member Post author
>>
I started off with TSP in my mind and while developing in XI, seeing the technical complexities, I first decided to find only the shortest distance and also avoided the back trip which happened to be Minimum Spanning tree.

When I was totally involved in developing this, I completely forgot that, the reduced version of Traveling salesman problem is nothing but Minimum spanning tree.

u made a small mis-assumption… MST isn’t reduced version of TSP.If it was true then most research going on TSP will be out of funds
..as I mentioned in my 1st comment TSP deals with roundtrip and shortest distance b/w nodes…whereas MST deals with the minimum weight of tree…like IRC for spreading messages in the tree..where each node will receive the message…the traversal path
is optimal path in MST..because the execution time is polynomial…where as in TSP it’s exponential
(for large nodes..no guaranteed solution)
Regards,
Sudhir

(0)
1. Sudhir,
I was a bit confused when you said Minimum Spanning tree and I even updated my blogs. Actually, it is Shortest Path Problem. Also, TSP is a kind of shortest path problem!

Hence, shortest path problem is a reduced version of Traveling sales man problem.
Regards,
Felix
(0)
1. Former Member Post author
>>shortest path problem is a reduced version of Traveling sales man problem.

Exactly…that’s what i initially wondered why u changed title to MST…but in blog as u specified abt spreading info.
Spreading info is always MST…say if u want to spread a rumor …in a city with 50-60 friends…
then the spanning of rumor/message in entire friend’s network with minimum cost is MST…but finding out shortest distance b/w two friends is Shortest path problem (SPP)…and traveling ALONE
with shortest roundtrip distance is TSP

Regards,
Sudhir

(0)
2. Former Member Post author
>>
I started off with TSP in my mind and while developing in XI, seeing the technical complexities, I first decided to find only the shortest distance and also avoided the back trip which happened to be Minimum Spanning tree.

When I was totally involved in developing this, I completely forgot that, the reduced version of Traveling salesman problem is nothing but Minimum spanning tree.

u made a small mis-assumption… MST isn’t reduced version of TSP.If it was true then most research going on TSP will be out of funds
..as I mentioned in my 1st comment TSP deals with roundtrip and shortest distance b/w nodes…whereas
MST deals with the minimum weight of tree…like IRC for spreading messages in the tree..where each
node will receive the message…the traversal path
is optimal path in MST..because the execution time is polynomial…where as in TSP it’s exponential
(for large nodes..no guaranteed solution)
Regards,
Sudhir

(0)
2. The aim of the blog is neither to show how XYZ algorithm which can be done in XI nor to market XI to companies implementing TSP algo.

The aim of the blog is to show how XI can be used in transforming values having same data structure and doing a data lookup on the same XML, only by using message mapping, without any advanced module programing or java libs. The aim is mostly on technical perspective rather than business perspective, giving an outlook of ResultList usage and XML context changes to extreme limits. To demonstrate this, TSP (MST) is taken as an example. This blog series has nothing to do with business or marketing, but I promise that its going to be a good feast for a technical developer.

Yes, its Minimal Spanning Tree(MST) and I have updated (updating…). I totally forgot that TSP have return routes ;).

>> Anyways my point is…here it fails to give a true business motive for above blog

The blog doesn’t have any business motive. It only has pure technical motives ๐

(0)