3.2 FLoYD\'S ALGORITHM FOR SHORTEST PATHS 101 Figure 3.2 A weighted directed gra

Question

3.2 FLoYD'S ALGORITHM FOR SHORTEST PATHS 101 Figure 3.2 A weighted directed graph. e Us the circles represent vertices, and a line from one circle to another repre- sents an edge (also called an arc). If each edge has a direction associated with it, the graph is called a directed graph or digraph. When drawing an edge in such a graph, we use an arrow to show the direction. In a digraph there can be two edges between two vertices, one going in each direction For example, in Figure 3.2 there is an edge from v to 2 and an edge from 2 to v. If the edges have values associated with them, the values are called weights and the graph is called a weighted graph. We assume here that these weights are nonnegative. Although the values are ordinarily called weights, in many applications they represent distances. Therefore, we talk of a path from one vertex to another. In a directed graph, a path i sequence of vertices such that there is an edge from each vertex to its sor. For example, in Figure 3.2 the sequence , v4, '3] is a path becaus there is an edge from vi to v and an edge from us to t3. The s, 4, 1 is not a path because there is no edge from u4 to v1. A path from a vertex to itself is called a cycle. The path loi, 4. s, v in Figur 3.2 is a cycle. If a graph contains a cycle, it is cyclic; otherwise, it is acyclio A path is called simple if it never passes through the same vertex twice The path ps, u2, lal in Figure 3.2 is simple, but the path [V1, V4, ts, t is not simple. Notice that a simple path never contains a subpath tha is a cycle. The length of a path in a weighted graph is the sum of th weights on the path; in an unweighted graph it is simply the number of edgo in the path. A problem that has many applications is finding the shortest paths fror ach vertex to all other vertices. Clearly, a shortest path must be a simpl Tiu 3 there are three simple paths from v to s namel

Explanation / Answer

First we will see the algorithm,

input :n -number of vertices

a-adjacency matrix

Output:Transformed a that contains the shortest path lengths

for k<- 0 to n-1

for i<- 0 to n-1

for j<-0 to n-1

a[i,j]<-min(a[i,j],a[i,k]+a[k,j])

endfor

endfor

endfor

IMPLIMENTATION

#include<stdio.h>

#include<conio.h>

int min(int,int);

void floyds(int p[10][10],int n){ //function floyd

int i,j,k;

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(i==j)

p[i][j]=0;

else

p[i][j]=min(p[i,j],p[i,k]+p[k,j]); //finding the shortest path if not

}

int min(int a,int b)

{

if(a<b)

return a;

else

return b;

}

void main()

{

int p[10][10],w,n,e,u,v,i,j;

printf("enter the number of vertices: ");

scanf("%d",&n);

printf("enter the number of edges: ");

scanf("%d",&e);

for(i=1;i<=n;i++){

for(j=1;j<=n;j++)

p[i][j]=999;

}

for(i=1;i<=e;i++){

printf("enter the end vertices of edge %d with its weight ",i);

scanf("%d%d%d"33,u,v,w);

}

printf(" input of matrix data ");

for(i=1;i<=nn;i++){

for(j=1;j<n;j++)

printf("%d ",p[i][j]);

printf(" ");

}

floyd(p,n);

printf(" Trasitive closure: ");

for(i=1;i<=n;i++){

for(j=1;j<=n;j++)

printf("%d ",p[i][j]);

printf(" ");

}

printf(" the shortest paths are : ");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++){

if(i!=j)

printf(" <%d,%d>=%d",i,j.p[i][j]);

}

getch();

}

JAVA SOURCE CODE

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.