HW8 Shortest Path

Generate 2D weight matrix using random numbers (Below shows an undirected graph)

Compute solutions (shortest distances) to the problem of "single source all destinations" where column "from" is the connection table in which from[j] stores the vertex who connects to j with the shortest edge 0<=j<=n-1

Report the shortest paths from the source to all destinations

Compute solutions (shortest distances) to the problem of "all pairs"

Compute the connection table for all vertices

Report the shortest paths for each pair of two vertices (I)

Report the shortest paths for each pair of two vertices (II)

The transitive closure of G

Generate 2D weight matrix using random numbers (Below shows another undirected graph)

Compute solutions (shortest distances) to the problem of "single source all destinations" where column "from" is the connection table in which from[j] stores the vertex who connects to j with the shortest edge 0<=j<=n-1

Report the shortest paths from the source to all destinations

Compute solutions (shortest distances) to the problem of "all pairs"

Compute the connection table for all vertices

Report the shortest paths for each pair of two vertices (Something is wrong here. Please find it out and figure out what is going on.)

Compute transitive closure using the weight matrix as the 0/1 adjacency matrix

Reduce the density of the edges in G' (which is directed) by proper parameters

The All pairs shortest paths of G' (The connectivity of vertices is sparse.)

The transitive closure of G'