What is the primary challenge in finding shortest paths in graphs with negative weight cycles?
The shortest path might involve traversing a cycle repeatedly to minimize the total weight.
The presence of cycles makes the graph too complex for efficient shortest path algorithms.
Standard shortest path algorithms are not designed to handle cycles.
Negative weights make it impossible to define a meaningful concept of 'shortest' path.
If a graph has negative weight cycles, what can we say about finding the shortest path?
Bellman-Ford algorithm will take significantly longer to find the shortest path.
The graph must be undirected to have negative weight cycles.
The shortest path is undefined as we can keep traversing the cycle, decreasing the path length infinitely.
Dijkstra's algorithm will always find the correct shortest path.
Consider a social network graph where vertices are users and edges are friendships. Which representation would be best for quickly finding all the friends of a particular user?
Edge List
Adjacency List
Adjacency Matrix
Incidence Matrix
Prim's algorithm for finding the MST starts with an arbitrary vertex. Does the choice of the starting vertex affect the final MST found?
Yes, different starting vertices may lead to different MSTs
No, the MST is unique for a given graph
In a weighted graph representing a road network with construction delays (represented by negative weights), what does finding the 'shortest path' mean?
Finding the path with the fewest road closures.
Finding the path with the least overall travel time, considering delays.
Finding the path with the lowest fuel consumption.
Finding the path with the shortest geographical distance.
You are tasked with designing a system to schedule tasks with dependencies between them. What graph data structure would be most appropriate to represent these dependencies?
Bipartite Graph
Directed Acyclic Graph (DAG)
Complete Graph
Undirected Graph
An incidence matrix for a graph with 'V' vertices and 'E' edges will have dimensions:
V x V
Depends on the graph's connectivity
E x E
V x E
What is the purpose of topological sorting in directed acyclic graphs (DAGs)?
Finding a linear ordering of vertices where for every edge (u, v), u comes before v.
Determining if the graph has a Hamiltonian cycle.
Calculating the minimum spanning tree of the graph.
Finding the shortest path between any two vertices.
In an undirected graph represented using an incidence matrix, what would be the sum of the values in a single column?
1
V (number of vertices)
0
2
Which of the following algorithms can handle negative weights in a weighted graph without issues?
Breadth-First Search (BFS)
Bellman-Ford Algorithm
Prim's Algorithm
Dijkstra's Algorithm