# 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

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

Written by fR0DDY

June 7, 2010 at 1:14 PM