Which of the following situations would make Bellman-Ford algorithm a better choice than Dijkstra's algorithm?
Finding the shortest path in an unweighted graph
Finding the shortest path in a graph with negative edge weights
Finding the shortest path in a dense graph
Finding the shortest path in a tree
In a graph with a large number of vertices but relatively few edges (sparse graph), which representation would be most space-efficient?
Adjacency Matrix
Edge List
None of the above
Incidence Matrix
Why are negative weights problematic for some shortest path algorithms?
These algorithms assume that adding an edge to a path always increases its total weight.
All of the above
Algorithms like Dijkstra's rely on the principle that shorter paths are always discovered before longer ones.
Negative weights can lead to cycles where the total weight decreases with each iteration, confusing the algorithm.
Which of the following real-world scenarios is best modeled using a weighted graph with potentially negative edge weights?
Finding the shortest route between two cities on a map
Modeling financial transactions where profits and losses are possible
Tracking the spread of information in a social network
Representing relationships in a family tree
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 shortest geographical distance.
Finding the path with the fewest road closures.
Finding the path with the lowest fuel consumption.
Finding the path with the least overall travel time, considering delays.
In an undirected graph represented using an incidence matrix, what would be the sum of the values in a single column?
0
1
2
V (number of vertices)
Prim's algorithm for finding the MST starts with an arbitrary vertex. Does the choice of the starting vertex affect the final MST found?
No, the MST is unique for a given graph
Yes, different starting vertices may lead to different MSTs
In the context of Kruskal's algorithm, what data structure is commonly used to efficiently detect cycles during edge addition?
Queue
Stack
Heap
Disjoint Union Set (Union-Find)
If you need to perform frequent edge insertions and deletions in a graph, which representation might be preferred?
It depends on the specific graph operations
How does the concept of 'distance' in a weighted graph differ from that in an unweighted graph?
Distance is only defined for unweighted graphs.
In weighted graphs, 'distance' always refers to geographical distance, while in unweighted graphs, it can represent abstract relationships.
There is no difference; 'distance' has the same meaning in both types of graphs.
In a weighted graph, 'distance' represents the sum of edge weights along a path, while in an unweighted graph, it's the number of edges.