Question - 1
a)
In the given problem, we are given a source 's' and a destination, 'd'. To find the shortest travel time between the given source and destination we can create a graph G with vertices as bus stops and roads as the edges.
Assuming, we are given a schedule of buses between all the bus stops, the arrival time and the departure time.
We can use modified Dijkstra's shortest path algorithm to find the shortest path, but to apply this algorithm we will construct our graph in such a way that for each node between the source and destination we will calculate the traveling time for each bus that is scheduled to visit that stop, adjacent bus stops (child nodes) and our destination.
We can calculate travel time or the edge weight by looking in the schedule like if the Bus B is supposed to start from Bus Stop L at 11:00 AM and reaches Bus Stop M at 11:15 AM so the edge weight becomes 15 minutes.
But to board Bus B from Bus Stop L the user might have to wait, so in the entire trip we can say
totalWaitTime = \(\sum_{i\ =s}^d\left(b.departureTime\ -\ b.arrivalTime\right)+initialWaitTime\)(taken care by the mapping system)
We will create the required graph using the Adjacency list, \(ADJ\)
We can create an array ADJ[0. . . n] for n vertices. Each of the array element will be a linked-list depicting the adjacent nodes.
Each item in the linked-list will be a an edge (u, v) such that u is the index of the ADJ list.
For the edgeWeights we will create a edge-matrix W such that each W[u][v] will depict the edge-weight. We will make is using the schedule given by MBTA.
We will look up in the schedule to get the transition time and add that to edgeWeight for that vertex.
b) The technical problem can be deduced to finding the shortest path from a single source. We will be using Dijkstra's algorithm to solve the problem.
c) We can compute the shortest path now with the graph we have constructed above.
In our graph the edge weights are the the time taken to reach from the vertex u to vertex v.
While performing dijkstra's algorithm from the source 's' we will perform it for all the buses or routes.
We will add initial wait time for each bus and then we will return the shortest path.
The algorithm maintains a
set S of vertices u for which we have determined a shortest-path distance d(u)
from s; this is the “explored” part of the graph. Initially S = {s}, and d(s) = 0.
Now, for each node v ∈ V−S, we determine the shortest path that can be
constructed by traveling along a path through the explored part S to some
u ∈ S, followed by the single edge (u, v). That is, we consider the quantity \(d'\left(v\right)=\min_{e=\left(u,v\right):u\in S}d\left(u\right)+W\left[u\right]\left[v\right]+v.waitTime\)()
Dijkstra's Algorithm
Dijkstra’s algorithm maintains a set S of vertices whose final shortest-path
weights from the source s have already been determined. The algorithm repeatedly
selects the vertex u 2 V S with the minimum shortest-path estimate, adds u
to S, and relaxes all edges leaving u. In the following implementation, we use a
min-priority queue Q of vertices, keyed by their d values.
\(\Pi\leftarrow\) An array with index depicting vertices with values as their parent.
\(W\leftarrow\) this is the edgeWeight matrix constructed using the given route schedule by the MBTA
DIJKSTRA(G, W, s, f, startTime) {
1. Initialize-Single-Source(G, W, s, f, startTime)
2. S = \(\emptyset\)
3. Q = min priority queue of vertices
4. while \(Q\ne\varnothing\)
5. u = EXTRACT-MIN(Q)
6. \(S=\) \(S\ \cup\left\{s\right\}\)
7. for each vertex \(v\ \in G.Adj\left[u\right]\)
8. RELAX(u,v,w, startTime)
9. Print "Minimum time to reach : "+ \(d\left[f\right]\)
10. printPath(\(\Pi\), f)
RELAX(u, v, W, startTime ){
1. if d[v] > d[u] + W[u][v] + v.waitTime()
2. \(d\left[v\right]=d\left[u\right]+W\left[u\right]\left[v\right]\)+ v.waitTime()
3. \(\Pi\left[v\right]\leftarrow u\) // Storing the parent of the node in the array \(\Pi\)
}
PRINT-PATH(\(\Pi\), f){
1. // base case: if 'f' is source
2. if \(\Pi\left[f\right]\) == -1:
3. return
4. PRINT-PATH(\(\Pi,\ \Pi\left[f\right]\))
5. Print(f)
}
d)
Time Complexity: The time complexity of the above algorithm can be given as \(O\left(\left|V\right|\log\right|V\left|+\left|E\right|\log\left|V\right|\right)\)
Space Complexity: The space complexity can be computed as in the adjacency list, for each vertex u there can be v vertices and there can be as many as B buses that can stop at a vertex . \(O\left(V^2B\right)\)
e)
In the given problem we start by creating a graph by the given schedule timings of the buses. We create the graph in such a way that the edge weights represent the travel time between the stops. We give this graph, source and destination, input to the Dijkstra algorithm which finds the shortest path between the source and the destination. We make the required changes to the edge-relaxation technique to get the correct edge weights. That is we add the transition times and the wait times in the journey. We know the edge weights calculated so far in the graph are correct, on applying Dijkstra's Algorithm we get the correct path as we know Dijkstra's algorithm works correctly.
2. a)
We are given a network N of wires such that B \(⊆\) N, B is a spanning tree of N, to create a minimum spanning tree of B we need to find edges that we need to remove from B that are not in T, the MST we have to create and we need to find the edges that are in T but not in B, those edges we need to add to B. While adding the edge we need to check if that forms a cycle, if it does then we discard that edge and put it back to its original position.
Assumption: We are given two lists that contain the edges in B and T, \(E_B\) and \(E_T\).
ALGORITHM
1. Create a set \(addEdge=\left\{\right\}\) that will store the edges that are to be added to B to make it a MST
2. Create a set \(removeEdge=\left\{\right\}\) that will store the edges that are to be removed from B to make it a MST
3. \(i=0,\ j=0\)
3. while (\(i<\left|E_B\right|\ \ and\ j<\left|E_T\right|\)) {
4. \(e_B\) =\(E_B.get\left(i\right)\)
5. \(e_T\) = \(E_T.get\left(j\right)\)
6. if \(e_B\ \notin E_T\):
7. \(removeEdge.add\left(e_B\right)\)
8. if \(e_T\notin E_B\):
9. \(addEdge.add\left(e_T\right)\)
}
// Now we have the edges that we need to remove and the edges that we need to add to make a MST.
1. For each edge \(e_R\) in \(removeEdge\):
2. \(E_B.remove\left(e_R\right)\)
3. For each edge \(e_A\) in \(addEdge:\)
4. \(E_B.add\left(e_A\right)\)
// We can find if it contains a cycle by applying DFS or Union-Find algorithm
5. If including this edge doesn't cause a cycle then
6. add this edge in \(E_B\)
7. Print "Connect wire from \(e_A.src\) to \(e_A.dest\)"
8. else:
9. \(E_B.add\left(e_R\right)\)
\(E_B.remove\left(e_A\right)\)
b)
In the above algorithm we first find all the edges that are not present in T. T is our MST so we need to convert B to T. If we directly remove all the edges \(e_R\) \(\in edgeRemove\) that are not in T we will end up disconnecting the network. So we also find the edges that are in T i.e \(e_A\in addEdge\) but not in B. So for every edge we remove we add an edge to keep the network connected. So this creates a spanning tree every time we exchange an edge if adding that edge does not create a cycle. If it does we exchange the original edges back.
So our algorithm terminates as the size of Edges in B is finite and it terminates and it ends up creating T as we add those edges that are in T and removing edges that are not in T.
c)
Since we are converting a spanning tree into a Minimum Spanning Tree, So T, which is our Minimum Spanning Tree, all the edges in T if added to B and all the edges that are not in T removed from B would only reduce the latency and make the network better. It is not possible to add an edge from T which would increase the overall latency since that edge belongs to a Minimum Spanning Tree.