# COME ON CODE ON

A blog about programming and more programming.

## All Pair Shortest Path (APSP)

with one comment

Question : Find shortest paths between all pairs of vertices in a graph.

Floyd-Warshall Algorithm
It is one of the easiest algorithms, and just involves simple dynamic programming. The algorithm can be read from this wikipedia page.

```#define SIZE 31
#define INF 1e8
double dis[SIZE][SIZE];
void init(int N)
{
for (k=0;k<N;k++)
for (i=0;i<N;i++)
dis[i][j]=INF;
}
void floyd_warshall(int N)
{
int i,j,k;
for (k=0;k<N;k++)
for (i=0;i<N;i++)
for (j=0;j<N;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

int main()
{
//input size N
init(N);
//set values for dis[i][j]
floyd_warshall(N);
}```

We can also use the algorithm to

1. find the shortest path
• we can use another matrix called predecessor matrix to construct the shortest path.
2. find negative cycles in a graph.
• If the value of any of the diagonal elements is less than zero after calling the floyd-warshall algorithm then there is a negative cycle in the graph.
3. find transitive closure
• to find if there is a path between two vertices we can use a boolean matrix and use and-& and or-| operators in the floyd_warshall algorithm.
• to find the number of paths between any two vertices we can use a similar algorithm.

NJOY!!
-fR0DDY

Written by fR0DDY

August 7, 2010 at 1:53 PM

## Convert a number from decimal base to any Base

Convert a given decmal number to any other base (either positive or negative).

For example, 100 in Base 2 is 1100100 and in Base -2 is 110100100.

Here’s a simple algorithm to convert numbers from Decimal to Negative Bases :

```def tonegativeBase(N,B):
digits = []
while i != 0:
i, remainder = divmod (i, B)
if (remainder < 0):
i, remainder = i + 1, remainder + B*-1
digits.insert (0, str (remainder))
return ''.join (digits)```

We can just tweak the above algorithm a bit to convert a decimal to any Base. Here’s a sample code :

```#include<iostream>
using namespace std;

void convert10tob(int N,int b)
{
if (N==0)
return;

int x = N%b;
N/=b;
if (x<0)
N+=1;

convert10tob(N,b);
printf("%d",x<0?x+(b*-1):x);
return;
}

int main()
{
int N,b;
while (scanf("%d%d",&N,&b)==2)
{
if (N!=0)
{
convert10tob(N,b);
printf("\n");
}
else
printf("0\n");
}
}
```

NJOY!
-fR0DDY

Written by fR0DDY

February 17, 2010 at 6:06 PM

Posted in Algorithm, Maths, Programming

Tagged with , , , , ,