You are building a flight routing system. What graph algorithm can you use to find the cheapest flight itinerary with potentially multiple layovers?
A* Search Algorithm
Dijkstra's Algorithm
Bellman-Ford Algorithm
Depth-First Search (DFS)
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
Tracking the spread of information in a social network
Representing relationships in a family tree
Modeling financial transactions where profits and losses are possible
What is the primary distinction between an unweighted graph and a weighted graph?
Unweighted graphs are always undirected, while weighted graphs are always directed.
Unweighted graphs have a fixed number of vertices, while weighted graphs can have a variable number of vertices.
Unweighted graphs are used for simple relationships, while weighted graphs are used for complex mathematical computations.
Unweighted graphs represent connections, while weighted graphs represent connections with associated costs or distances.
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 lowest fuel consumption.
Finding the path with the least overall travel time, considering delays.
Finding the path with the fewest road closures.
Which of the following situations would make Bellman-Ford algorithm a better choice than Dijkstra's algorithm?
Finding the shortest path in a dense graph
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 tree
Which of the following algorithms is typically used for topological sorting?
Kruskal's algorithm
Dijkstra's algorithm
Prim's algorithm
What value is stored in the cells of an incidence matrix to represent that a vertex is NOT incident to an edge?
0
Infinity
-1
1
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
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?
Directed Acyclic Graph (DAG)
Undirected Graph
Bipartite Graph
Complete Graph
Which representation would be most suitable for a graph where you primarily need to iterate over all edges efficiently?
Adjacency List
Adjacency Matrix
Edge List
Incidence Matrix