COMP 3270代做、代写Algorithms留学生、代做Java程序语言、c/c++，Python代写

日期：2019-04-24 11:04

COMP 3270 Introduction to Algorithms

Homework 3

1. BFS

a. Run Breadth First Search on the directed graph below using vertex 3 as the source. Show

the priority queue after each iteration of the while loop and the final d values.

b. Explain briefly why the complexity of BFS is O(V+E). Dijkstra’s Algorithm

Problem 24.3-1 on page 662 of textbook (third edition). You don’t need to do the second

part, i.e. running again using vertex z as the source.

3. Bellman-Ford Algorithm

Consider the following graph

a. Give the adjacency matrix of the graph.

b. Run Bellman-Ford algorithm on the graph, using vertex a as the source. In each pass,

relax the edges in the order (a, b), (a, c), (d, b), (c, d), (b, e), (e, d). Use pages 5-25 of

Lecture nodes 10 or Figure 24.4 on page 652 of textbook as an example.