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.)
-
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 ≤ ≤ ?
