5. Decision Mathematics

Graphs Networks — Quiz

Test your understanding of graphs networks with 5 practice questions.

Practice Questions

Question 1

In an undirected weighted graph with non-negative edge weights and represented using adjacency lists, what is the time complexity of Dijkstra’s algorithm when implemented with a Fibonacci heap?

Question 2

Which algorithm finds single-source shortest paths in a directed acyclic graph with $O(V+E)$ time complexity?

Question 3

Given the weighted directed acyclic graph with vertices $\\{1,2,3,4\\}$ and edges $1\to2$ (2), $1\to3$ (5), $2\to3$ (1), $2\to4$ (2), $3\to4$ (1), what is the shortest path length from vertex 1 to vertex 4?

Question 4

In which algorithm does each of the $E$ edges get relaxed exactly $V-1$ times in the worst case, resulting in a time complexity of $O(VE)$ for single-source shortest paths when negative weights but no negative cycles are allowed?

Question 5

What is the time complexity of Johnson’s algorithm for all-pairs shortest paths on a directed graph with $V$ vertices and $E$ edges?