ASSIGNMENT 3 WRITTEN Solution

$30.00

Description

1. Consider the following weighted, directed graph . There are 7 vertices and 10 edges. The edge list

is as follows:

4

( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , )

3

2

9

8

1

2

2

1 4

The Bellman-Ford algorithm makes | | − 1 = 7 − 1 = 6 passes through the edge list . Each pass relaxes the edges in the order they appear in the edge list. As with Dijkstra’s algorithm, we record the current best known cost [ ] to reach each vertex from the start vertex . Initially [ ] = 0 and [ ] = +∞ for all the other vertices. Run Bellman-Ford on the given graph, starting at vertex , and using the order of set above, show me the contents of array [] after each iteration (6 arrays in all.)

  1. Design an efficient algorithm (i.e. write pseudocode) for finding a longest directed path from a vertex to a vetex of a directed acyclic graph . Specify the graph representation used (adjacency matrix, adjacency list, etc.) and any auxiliary data structures used. Analyze the worst-case running time of your algorithm.

  1. The table below purports to give the length of the shortest routes connecting the cities. It contains an error. Correct the table and draw the corresponding map. (Assume it’s undirected).

Providence

Westerly

New London

Norwich

Providence

0

53

54

48

Westerly

53

0

18

101

New London

54

18

0

12

Norwich

48

101

12

0

  1. Suppose we are given an unweighted, directed graph with vertices (labelled 1 to ), and let be the × adjacency matrix for (that is, ( , ) = 1 if directed edge ( , ) is in and 0 otherwise). a. Let the product of with itself ( 2) be defined, for 1 ≤ , ≤ , as follows:

2( , ) = ( ( , 1) ∙ (1, )) + ( ( , 2) ∙ (2, )) + ⋯+ ( ( , ) ∙ ( , ))

where “” is the Boolean and operator and “+” is the Boolean or operator. Given this definition what does 2( , ) = 1 imply about vertices i and j? What if 2( , ) = 0?

    1. Suppose 4 is the product of 2 with itself. What do the entries of 4 signify? What about for any 1 ≤ ≤ ?

  1. Now consider a weighted, directed graph with vertices and its corresponding adjacency matrix

, where ( , ) = 0 if = , ( , ) = ℎ (( , )) if ( , ) is in and ( , ) = ∞ otherwise. Here, let

2 = min{ ( , 1) + (1, ), ( , 2) + (2, ), … , ( , ) + ( , )}

where + is regular addition. If 2( , ) = , what may we conclude about vertices and ? What about for any 1 ≤ ≤ ?


error: Content is protected !!