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.)
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.
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
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?
Suppose 4 is the product of 2 with itself. What do the entries of 4 signify? What about for any 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 ≤ ≤ ?
