## 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.

- Feeding the input with XML
- Try to loop back to XI itself for recursive like functions.
- Usage of BPM
- 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.

Community UserPost author>>Please give me your valuable comments on my TSP implementation on XI.

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?

Let me start with small example, an ABC courier

services is going to setup 4 branches in Indian

cities namely Hyderabad,Mumbai,Bangalore and

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

convinced to buy XI instead of developing an application

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

node receives message.

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

Community UserPost authorWell..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

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

Community UserPost 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

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!

ref: http://en.wikipedia.org/wiki/Shortest_path

Hence, shortest path problem is a reduced version of Traveling sales man problem.

Regards,

Felix

Community UserPost authorExactly…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

Community UserPost 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

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 ðŸ˜‰