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];
}
}
}
}

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;
}
}
}