Archive for August, 2007

Floyd Warshall Algorithm!


The Floyd-Warshall Algorithm is an efficient algorithm to find all-pairs shortest paths on a graph. That is, it is guaranteed to find the shortest path between every pair of vertices in a graph. The graph may have negative weight edges, but no negative weight cycles (for then the shortest path is undefined).

This algorithm can also be used to detect the presence of negative cycles—the graph has one if at the end of the algorithm, the distance from a vertex v to itself is negative.

The problems form ACM UVA , 523 and 627

Assuming that a[i][j]=-1 where there is no path. p[i][j] is used for tracing the shortest path. The Algorithm is just an application of Dynamic Programming. INF is considered to be a very big integer.

for(int i=0;i<n;++i)
for(int j=0;j<n;j++)
if (a[i][j]==-1)
{
a[i][j]=INF;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
p[i][j]=i;
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i][j] > a[i][k]+a[k][j])
{ a[i][j]=a[i][k]+a[k][j];
p[i][j]=p[k][j];
}
}
}
}

Leave a comment

Longest path!


The problem taken form acm uva site , Longest Path

Since we need to know the longest path for a source node given, the graph of cities to be traversed in DFS. The Depth First Traversal visits all nodes reachable from the source node. Here is the function needed for DFS in this problem.

void dfs(long snode)
{
long i;
if(sum>max)
{
max=sum;
p=snode;
}
for(i=0;i<num;i++)
{
if(n[snode][i]==1&&visited[snode][i]==0&&i!=start)
{
visited[snode][i]=1;
sum++;
dfs(i);
sum--;
visited[snode][i]=0;
}
}
}

dfs.png

1 Comment

Threaded binary Trees !!


Traversing the binary tree is the most important operation and used in almost every application. The iterative implementation of traversing the binary tree is implemented using either stack (simulation of recursion) or using the threaded binary trees , later being the more efficient. The idea is to maintain extra information of a particular traversal which saves a lot of pushing and popping in stack implementation. This is done by maintaining extra pointer to the leaf nodes (right child in case of right-in threaded binary tree, named on the basis of same) known as thread . This is done as follows:

While adding a left child in right-in threaded binary tree

– Point the right child of the node to its parent.

While adding a right child in right -in threaded binary tree

-Point the right child of the node to the thread of the parent

The thread is detected from the normal links by using a boolean field in the node , when set to true indicates that it is actually a thread .

Here is the implementation
struct tnode *insert(struct tnode *p , int val)
{
if(p==NULL)
{
p = (struct tnode *)malloc(sizeof(struct tnode));
p->data = val;
p->left = NULL;
p->right = NULL;
p->rthread=true;
}
else
{
struct tnode *q,*temp;
q=p;
temp=p;
while(q != NULL && q->rthread==false)
{
temp= q;
if( val >= temp->data )
q=temp->right;
else if( val < temp->data )
q=temp->left;
}
struct tnode *n;
n= (struct tnode *)malloc (sizeof(struct tnode));
n->data =val;
if( val >=temp->data )
{
if(temp->rthread)
{
struct tnode *r;
r=temp->right;
temp->right =n;
temp->rthread=false;
n->left=NULL;
n->right=r;
n->rthread=true;
}
}
else
{
temp->left = n;
n->left=NULL;
n->right=temp;
n->rthread=true;
}
}
return p;
}

A left-in-threaded binary tree  may be defined similarly, as one in which each NULL left pointer  is altered to contain a thread to that node’s inorder predecessor. An in-threaded binary tree may then be defined as a binary tree that is  both left in-threaded and right in-threaded. 

2 Comments

Kopete and Latex


Latex has been the best typesetting software ever made. I have always preferred it for any type of document. Latex has been very useful in case you want to use many mathematical formulas in the document. Sometimes, though rarely :D, we need to use mathematical expressions in our chat conversation. I was wondering if any messenger provides the \Latex support in the chat window. Then I found kopete’s ” KopeTeX” plugin allows Kopete to render Latex \
formulas in the chat window. The sender must enclose the formula between two $ signs. \
ie: $$formula$$ +This plugin requires ImageMagick convert program installed in order.

For example: for T= 2 PI /OMEGA

$$T=2\frac{\pi}{\omega}$$



kopete3.jpg

kopete11.jpg

1 Comment

Merging two sorted linked lists !!


The problem is just like merging step in merge sort, wherein we have two sorted arrays and merge them into one. If you haven’t already gone through the linked list concepts, I would recommend you to go through that first. The algorithm is simple and stated as:


struct node *merge(struct node *p,struct node *q)
{
        struct node *r,*s;
        struct node *a=NULL;
        r=p; s=q;
        while(r !=NULL && s!= NULL)
        {
                if(r->data <= s->data)
                {
                        a=insert(a,r->data);
                        r=r->link;
                }
                else{
                        a=insert(a,s->data);
                        s=s->link;
                }
        }
        if(r==NULL)
                while(s!=NULL)
                {
                        a=insert(a,s->data);
                        s=s->link;
                }
        else
                while(r!=NULL)
                {
                        a=insert(a,r->data);
                        r=r->link;
                }
        return a;
}

3 Comments