Question

true/false

		An unweighted path length measures the number of edges in a graph.
		Breadth first search traverses the graph in "layers", beginning with the closest nodes to the ending location first.
		The computer knows about neighbors by checking the graph storage (such as the adjacency matrix or the adjacency list).
		Breadth first traversals use a stack to process nodes.
		The weighted path length is the sum of the edge costs on a path.
		Dijkstra's shortest path algorithm can be used to find the shortest path in a weighted graph with positive edges.
		Dijkstra's shortest path algorithm uses a FIFO queue like the BFS.
		A negative cost cycle means that we can keep shortening a path by going in an infinite loop.
		Graphs with negative edge costs, but no negative cost cycle, can use Bellman-Ford's shortest path algorithm.
		A topological sort orders verticies in a DAG so that if there is a path from node 1 to node 2, node 2 comes before node 1.
		A graph with a cycle cannot have a topological sort.
		The in-degree of a node is the number of incoming edges.
		Critical path analysis is another method for calculating the shortest path.
		Slack time is the amount of time a task can be delayed without delaying the project.
		Zero slack activities are on the critical path.

Answer 1

False.

• The unweighted path length gives the shortest distance.

True.

• BFS traverse graph in layers.

True

• The computer can know about neighbors by using graph storage.

False.

• BFS uses a queue for the traversal.

True

• It is the sum of edge costs.

True

• Dijkstra’s algorithm work with positive edges.

False

• Dijkstra’s algorithm uses a priority queue like BFS.

False

• The negative cost cycle means the overall sum of the cycle is negative.

True.

• A graph with a negative edge can use the Bellman-Ford algorithm.

True

• Topological sorting for DAG is a linear ordering of vertices.

True

• Graph having cycle cannot do the topological sort.

True

• In-degree means incoming edges.

False

• Critical path analysis is for calculating the longest path.

True

• It is the time by which a task can be delayed without delaying the project

False

• Activities on zero slack cannot be delayed.