Posts Tagged ‘Programming’
All Pair Shortest Path (APSP)
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
- find the shortest path
- we can use another matrix called predecessor matrix to construct the shortest path.
- 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.
- 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
Share this:
Number of Cycles in a Graph
Question : Find the number of simple cycles in a simple graph.
Simple Graph – An undirected graph that has no loops and no more than one edge between any two different vertices.
Simple Cycle – A closed (simple) path, with no other repeated vertices or edges other than the starting and ending vertices.
Given a graph of N vertices and M edges, we will look at an algorithm with time complexity O(2NN2). We will use dynamic programming to do so. Let there be a matrix map, such that map[i][j] is equal to 1 if there is a edge between i and j and 0 otherwise. Let there be another array f[1<<N][N] which denotes the number of simple paths.
Let, i denote a subset S of our vertices k be the smallest set bit of i then f[i][j] is the number of simple paths from j to k that contains vertices only from the set S.
In our algorithm first we will find f[i][j] and then check if there is a edge between k and j, if yes, we can complete every simple path from j to k into a simple cycle and hence we add f[i][j] to our result of total number of simple cycles.Now how to find f[i][j].
For very subset i we iterate through all edges j. Once we have set k, we look for all vertices 'l' that can be neighbors of j in our subset S. So if l is a vertex in subset S and there is edge from j to l then f[i][j] = f[i][j] + the number of simple paths from l to i in the subset {S – j}. Since a simple graph is undirected or bidirectional, we have counted every cycle twice and so we divide our result by 2. Here's a sample C++ code which takes N, M and the edges as input.
#include<iostream>
using namespace std;
#define SIZE 20
bool map[SIZE][SIZE],F;
long long f[1<<SIZE][SIZE],res=0;
int main()
{
int n,m,i,j,k,l,x,y;
scanf("%d%d",&n,&m);
for (i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
x--;y--;
if (x>y)
swap(x,y);
map[x][y]=map[y][x]=1;
f[(1<<x)+(1<<y)][y]=1;
}
for (i=7;i<(1<<n);i++)
{
F=1;
for (j=0;j<n;j++)
if (i&(1<<j) && f[i][j]==0)
{
if (F)
{
F=0;
k=j;
continue;
}
for (l=k+1;l<n;l++)
{
if (i&(1<<l) && map[j][l])
f[i][j]+=f[i-(1<<j)][l];
}
if (map[k][j])
res+=f[i][j];
}
}
printf("%lld\n",res/2);
}
NJOY!
-fR0DDY
Share this:
Number of Distinct LCS
This problem appeared in the November edition of CodeChef Monthly Contest. The problem is to find the number of distinct LCS that can be formed from the given two strings. A nice tutorial about it is given on the CodeChef site itself. Also there is a research paper available here. Here’s my solution to the CodeChef problem.
#include<iostream>
using namespace std;
int L[1005][1005];
int D[1005][1005];
int LCS(string X,string Y)
{
int m = X.length(),n=Y.length();
int i,j;
for (i=0;i<=m;i++)
{
for (j=0;j<=n;j++)
{
if (i==0 || j==0)
L[i][j]=0;
else
{
if (X[i-1]==Y[j-1])
L[i][j]=L[i-1][j-1]+1;
else
L[i][j]=max(L[i][j-1],L[i-1][j]);
}
}
}
return (L[m][n]);
}
int NLCS(string X,string Y)
{
int m = X.length(),n=Y.length();
int i,j;
for (i=0;i<=m;i++)
{
for (j=0;j<=n;j++)
{
if (i==0 || j==0)
D[i][j]=1;
else
{
D[i][j]=0;
if (X[i-1]==Y[j-1])
{
D[i][j]=D[i-1][j-1];
}
else
{
if (L[i-1][j]==L[i][j])
D[i][j]=(D[i][j]+D[i-1][j])%23102009;
if (L[i][j-1]==L[i][j])
D[i][j]=(D[i][j]+D[i][j-1])%23102009;
if (L[i-1][j-1]==L[i][j])
{
if (D[i][j]<D[i-1][j-1])
D[i][j]+=23102009;
D[i][j]=(D[i][j]-D[i-1][j-1]);
}
}
}
}
}
return (D[m][n]);
}
int main()
{
string X,Y;
int T,A,B;
scanf("%d",&T);
while (T--)
{
cin>>X>>Y;
A=LCS(X,Y);
B=NLCS(X,Y);
printf("%d %d\n",A,B);
}
}
NJOY!
-fR0DDY
Share this:
Subsequence Frequency
The question is to find the number of times a string appears as a subsequence in an another string. A similar question was asked in Google Code Jam 09. Here is the link.
So how do we do it. If you think the general way the first brute force method which comes to mind is to get a matrix for the general subsequence problem and then backtrack all paths that lead to the subsequence. But the backtracking will be too time consuming. Now the second thought which comes to mind is can’t we have a similar dynamic programming approach to find the frequency rather than length. Yes, thankfully we can do that. How?
First lets start with a string of two letters. Suppose we need to find the occurence of ab in abbacb. We can calculate the answer to be four. How did we do it, there are three b’s after first ‘a’ and only one after the second ‘a’, all in all four. So if somehow we manipulate the table to deal with the frequency of characters we can take out the total numbers of times the string appears as subsequence. If you wan’t to try out the algorithm for yourself, now is the right time. What follows next is the algorithm.
We have the table for the above example as :
| a | b | b | a | c | b | ||
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | |
| a | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| b | 0 | 0 | 1 | 2 | 2 | 2 | 4 |
As seen above we set the row[0] values to 1 and column[0] values to 0. Here’s the algorithm.
Let’s call the string whose frequency is to be found as str1 and given string str2.
for i from 1 to length(str1)
{
for j from 1 to length(str2)
{
if (str1[i-1]==str2[j-1])
table[i][j]=table[i-1][j]+table[i][j-1];
else
table[i][j]=table[i][j-1];
}
}
Here’s a C++ code for the Code Jam Question :
#include
using namespace std;
char str[1000],cj[]="welcome to code jam";
int M[30][1000]={0};
int main()
{
int t,i,j,k,l,lcj=strlen(cj);;
scanf("%d\n",&t);
for (j=1;j<=1000;j++)
M[0][j]=1;
for (j=1;j<=lcj;j++)
M[j][0]=0;
for (k=1;k<=t;k++)
{
gets(str);
l=strlen(str);
for (i=1;i<=lcj;i++)
{
M[i][0]=0;
for (j=1;j<=l;j++)
if (cj[i-1]==str[j-1])
M[i][j]=(M[i-1][j]+M[i][j-1])%10000;
else M[i][j]= M[i][j-1];
}
printf("Case #%d: %04d\n",k,M[lcj][l]);
}
}
Happy Coding!
-fR0D
COME ON CODE ON 