Dijkstra with unknown edge weight

A question is this type if and only if it involves finding the value or range of an unknown edge weight (often denoted x or y) based on conditions about shortest paths.

5 questions · Standard +0.8

7.04a Shortest path: Dijkstra's algorithm
Sort by: Default | Easiest first | Hardest first
Edexcel D1 Q3
8 marks Challenging +1.2
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{63f3ba38-8bca-4684-957f-aca7104f2f3e-03_734_1353_196_317} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} Figure 1 shows a graph in which \(y \geq 0\).
Given that the graph is a weighted network,
  1. find the range of values for the path of lowest weight from \(S\) to \(T\). Given instead, that the graph is a capacitated network with the numbers representing the capacity along each arc,
  2. find the range of values for the maximum flow from \(S\) to \(T\).
  3. Give an example of a practical problem which could be solved by using:
    1. the weighted network in part (a),
    2. the capacitated network in part (b).
Edexcel D1 2017 January Q6
9 marks Standard +0.8
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-07_1052_1447_212_310} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 4 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road. Stieg wishes to minimise the time spent driving from his home at A , to his office at H . The amount of traffic on two of the roads leading into H varies each day, and so the length of time taken to drive along these roads is expressed in terms of \(x\), where \(x > 7\)
  1. Use Dijkstra's algorithm to find the possible routes that minimise the driving time from A to H . State the length of each route, leaving your answer in terms of \(x\) where necessary.
    (7) On a particular day, the quickest route from A to H via G is 2 minutes quicker than the quickest route from A to H via E .
  2. Calculate the value of \(x\). You must make your method and working clear.
Edexcel D1 2020 June Q7
11 marks Challenging +1.2
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{3aa30e8f-7d55-4c3b-8b2c-55c3e822c8a0-08_645_1474_221_285} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} [The total weight of the network is \(205 + 3 x\) ] Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road. Malcolm wishes to minimise the time spent driving from his home at A to his office at H . The delays from roadworks on two of the roads leading in to H vary daily, and so the time taken to drive along these roads is expressed in terms of \(x\), where \(x\) is fixed for any given day and \(x > 0\)
  1. Use Dijkstra's algorithm to find the possible routes that minimise the driving time from A to H. State the length of each route, leaving your answer in terms of \(x\) where necessary. On Monday, Malcolm needs to check each road. He must travel along each road at least once. He must start and finish at H and minimise the total time taken for his inspection route. Malcolm finds that his minimum duration inspection route requires him to traverse exactly four roads twice and the total time it takes to complete his inspection route is 307 minutes.
  2. Calculate the minimum time taken for Malcolm to travel from A to H on Monday. You must make your method and working clear.
Edexcel D1 2022 June Q6
15 marks Challenging +1.2
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{27296f39-bd03-47ff-9a5e-c2212d0c68ed-08_832_1171_169_445} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} [The total weight of the network is \(383 + x\) ]
Figure 4 models a network of roads. The number on each edge gives the time, in minutes, to travel along the corresponding road. The vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\), H and J represent nine towns. Ezra wishes to travel from A to H as fast as possible. The time taken to travel between towns G and J is unknown and is denoted by \(x\) minutes. Dijkstra's algorithm is to be used to find the fastest time to travel from A to H. On Diagram 1 in the answer book the "Order of labelling" and "Final value" at A and J, and the "Working values" at J , have already been completed.
  1. Use Dijkstra's algorithm to find the fastest time to travel from A to H . State the quickest route. Ezra needs to travel along each road to check it is in good repair. He wishes to minimise the total time required to traverse the network. Ezra plans to start and finish his inspection route at A . It is given that his route will take at least 440 minutes.
  2. Use the route inspection algorithm and the completed Diagram 1 to find the range of possible values of \(x\).
  3. Write down a possible route for Ezra. A new direct road from D to H is under construction and will take 25 minutes to travel along. Ezra will include this new road in a minimum length inspection route starting and finishing at A . It is given that this inspection route takes exactly 488 minutes.
  4. Determine the value of \(x\). You must give reasons for your answer.
AQA D1 2011 January Q4
10 marks Moderate -0.3
The network below shows some paths on an estate. The number on each edge represents the time taken, in minutes, to walk along a path.
    1. Use Dijkstra's algorithm on the network to find the minimum walking time from \(A\) to \(J\). [6]
    2. Write down the corresponding route. [1]
  2. A new subway is constructed connecting \(C\) to \(G\) directly. The time taken to walk along this subway is \(x\) minutes. The minimum time taken to walk from \(A\) to \(G\) is now reduced, but the minimum time taken to walk from \(A\) to \(J\) is not reduced. Find the range of possible values for \(x\). [3]
\includegraphics{figure_4}