A network (or graph) is made up of vertices (points, also called nodes) connected by edges (lines), often used to model real systems like road maps, flight routes or computer networks. A weighted graph assigns a number (weight) to each edge — like distance, time or cost — and finding the shortest path means finding the route between two vertices with the smallest total weight, which algorithms like Dijkstra's can find systematically even in large, complex networks.
Example
A delivery company modelling its depots and drop-off points as a network, with edge weights representing driving time between each pair, can use a shortest-path algorithm to find the fastest route for a driver visiting multiple locations, rather than guessing.
Key terms
Vertex (node):
A point in a network, often representing a location or object.
Edge:
A connection between two vertices in a network.
Weighted graph:
A network where each edge has an associated value, like distance or cost.
Questions
1. A vertex in a network is:
A point, also called a node
A line connecting two points
A type of weight only
A colour used in diagrams
2. An edge in a network is:
A connection between two vertices
A single point with no connection
A type of weight measurement only
A completely unrelated shape
3. A weighted graph assigns:
A number to each edge, like distance or cost
No numbers to anything at all
A colour to each vertex only
A name to each edge, with no number
4. Networks can be used to model:
Road maps, flight routes or computer networks
Nothing measurable in the real world
Only abstract mathematical shapes with no real use
Only colours, with no other data
5. The shortest path problem finds:
The route between two vertices with the smallest total weight
The longest possible route between two vertices
A route with no vertices at all
The number of edges only, ignoring weight
6. A road map represented as a network would likely use edge weights for:
Distance or travel time
Only the road's colour
The number of cars on the road at this exact moment
Nothing at all; weights are never used for maps
7. Dijkstra's algorithm is used to:
Systematically find the shortest path in a network
Draw a network with no calculation involved
Delete vertices from a network
Add random weights to a network
8. In a network with vertices A, B, C, if edge A-B has weight 4 and edge B-C has weight 3, what is the total weight of a path from A to C via B?
7
4
3
12
9. If a direct edge from A to C has weight 8, and the path via B (from the previous question) has weight 7, the shortest path from A to C is:
Via B, with weight 7
Direct, with weight 8
Both paths are exactly equal
Neither path is valid
10. Why might a delivery company use a weighted graph rather than an unweighted one to plan routes?
Weights capture real differences like distance or time, which are needed to compare routes meaningfully
Weighted graphs are always identical to unweighted graphs in every way
Unweighted graphs always provide more useful route information
Delivery companies never need to compare different possible routes
11. A network representing friendships on a social media platform would likely use vertices to represent:
People
Only weights, with no vertices needed
Physical distances only
Colours only
12. Why can't the shortest path in a weighted graph always be found by simply counting the fewest number of edges?
A path with fewer edges might still have a higher total weight than a path with more, lower-weighted edges
The number of edges and the total weight are always exactly the same value
Counting edges always gives the mathematically correct shortest path
Weighted graphs never have more than one possible path between two vertices
13. Why is Dijkstra's algorithm considered more efficient than manually checking every possible path in a large network?
It systematically builds up shortest distances without needing to explore every single possible route combination
Manually checking every path is always faster in large networks
Dijkstra's algorithm and manual checking always take exactly the same amount of time
Efficient algorithms have no practical advantage over manual methods
14. Why might GPS navigation apps rely on shortest-path algorithms similar to Dijkstra's?
They need to quickly calculate optimal routes across huge, complex real-world road networks
GPS apps never use any form of network or graph modelling
Shortest-path algorithms have no relevance to real-world navigation
Navigation always relies on random route selection, not calculation
15. Why might Dijkstra's algorithm not work correctly on a graph with negative edge weights?
It assumes each step only increases total distance, an assumption negative weights would break
Negative weights have no effect on any shortest-path algorithm
All networks in the real world always have negative weights
Dijkstra's algorithm was specifically designed only for negative weights
16. Why might modelling a computer network as a weighted graph (with weights representing latency) help improve internet routing?
It allows data to be routed along paths with the lowest total delay, improving speed and reliability
Computer networks are never modelled using graphs or weights
Latency has no connection to how data is routed across a network
Routing decisions are always made completely randomly, with no calculation
17. In a network where vertex A connects to B (weight 5) and B connects to C (weight 2), and A also connects directly to C (weight 6), the shortest path from A to C is:
Direct, with weight 6
Via B, with weight 7
Both paths have identical weight
Neither path exists
18. A network used to model a public transport system would most likely use edge weights to represent:
Travel time or number of stops between stations
The colour of each train line only
The number of seats on a single train
Nothing measurable; transport networks are never weighted
19. Why might airlines use weighted networks to plan flight routes, with weights representing cost, distance or time?
It lets them systematically compare and optimise many possible route combinations across a large network
Airlines never need to compare or optimise any of their flight routes
Flight planning has no connection to network or graph modelling
Weighted networks can only represent physical distances, not cost or time
20. Why might a network with more vertices and edges require a more efficient algorithm than manually tracing every path by hand?
The number of possible paths grows rapidly as a network gets larger, making manual checking impractical
Larger networks always have exactly the same number of possible paths as smaller ones
Manual tracing becomes easier, not harder, as a network grows in size
Efficient algorithms are only useful for very small, simple networks
21. Why might removing a single vertex from a network sometimes disconnect other parts of the network entirely?
If that vertex was the only connection between two regions of the network, its removal breaks that link
Removing any vertex from a network always has no effect on connectivity
Every vertex in a network is always equally replaceable with no impact
Networks can never become disconnected under any circumstances
Answer key (parent copy)
1. A point, also called a node
2. A connection between two vertices
3. A number to each edge, like distance or cost
4. Road maps, flight routes or computer networks
5. The route between two vertices with the smallest total weight
6. Distance or travel time
7. Systematically find the shortest path in a network
8. 7
9. Via B, with weight 7
10. Weights capture real differences like distance or time, which are needed to compare routes meaningfully
11. People
12. A path with fewer edges might still have a higher total weight than a path with more, lower-weighted edges
13. It systematically builds up shortest distances without needing to explore every single possible route combination
14. They need to quickly calculate optimal routes across huge, complex real-world road networks
15. It assumes each step only increases total distance, an assumption negative weights would break
16. It allows data to be routed along paths with the lowest total delay, improving speed and reliability
17. Direct, with weight 6
18. Travel time or number of stops between stations
19. It lets them systematically compare and optimise many possible route combinations across a large network
20. The number of possible paths grows rapidly as a network gets larger, making manual checking impractical
21. If that vertex was the only connection between two regions of the network, its removal breaks that link