What is the primary challenge in finding shortest paths in graphs with negative weight cycles?
Standard shortest path algorithms are not designed to handle cycles.
The presence of cycles makes the graph too complex for efficient shortest path algorithms.
The shortest path might involve traversing a cycle repeatedly to minimize the total weight.
Negative weights make it impossible to define a meaningful concept of 'shortest' path.
Which of the following operations is typically less efficient with an edge list representation compared to an adjacency matrix?
Determining the degree of a vertex
Adding a new edge
Checking if the graph is connected
Finding all edges connected to a specific vertex
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
Adjacency Matrix
Edge List
Incidence Matrix
What is the primary application of topological sorting in computer science?
Scheduling tasks with dependencies
Finding the shortest path between two nodes
Detecting cycles in a graph
Finding the minimum spanning tree of a graph
An incidence matrix for a graph with 'V' vertices and 'E' edges will have dimensions:
Depends on the graph's connectivity
E x E
V x V
V x E
Which of the following real-world scenarios is best modeled using a weighted graph with potentially negative edge weights?
Tracking the spread of information in a social network
Modeling financial transactions where profits and losses are possible
Representing relationships in a family tree
Finding the shortest route between two cities on a map
Topological sorting is possible for which type of graph?
Directed acyclic graphs (DAGs)
Weighted graphs
Complete graphs
Undirected graphs
Which of the following is NOT a characteristic of a minimum spanning tree (MST)?
It may contain cycles
It connects all vertices in the graph
It has the minimum total edge weight
It is a tree (acyclic)
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
Which algorithm efficiently calculates the shortest paths between all pairs of nodes in a weighted graph, useful for analyzing network connectivity in social networks?
Floyd-Warshall Algorithm
Bellman-Ford Algorithm
Kruskal's Algorithm
Dijkstra's Algorithm