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.

The distance between two connected nodes in a graph is the
length (number of edges) of the shortest path connecting them. The
diameter of a connected graph is the maximum distance between any
two of its nodes. Let v be an arbitrary vertex in a graph G. If
every vertex is within distance d of v, then show that the diameter
of the graph is at most 2d.

Usually, Djikstra’s shortest-path algorithm is not used on
graphs with negative-weight edges because it may fail and give us
an incorrect answer. However, sometimes Djikstra’s will give us the
correct answer even if the graph has negative edges.
You are given graph G with at least one negative edge, and a source
s. Write an algorithm that tests whether Djikstra’s algorithm will
give the correct shortest paths from s. If it does, return the
shortest paths. If not, return ‘no.’...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 35 seconds ago

asked 4 minutes ago

asked 24 minutes ago

asked 51 minutes ago

asked 55 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago