Suppose you are given a map (graph G) of a well-dev eloped transportation system

Question

Suppose you are given a map (graph G) of a well-dev eloped transportation system such as Washington Subway, London Underground or Paris Metro. The time it takes the trains to travel between every pair of adjacent stations I and j is T[i][j] is given. In addition, trains stop at each station for loading and unloading of passengers. The train stop time S[i] depends on how busy the station is, and is known for every station. Develop an algorithm in clearly defined steps or pseudo-code for this transportation system such that when a passenger at a given station enters her his destination station, the algorithm finds the path with the minimum travel time. Assume die time to wait at a station for the train to arrive and to get on the train is W[i] = S[i]/2, and it also takes E[i]= S[i] 2 to exit at the destination.

Explanation / Answer

1. Read number of stations (n) and their names
   for(int i=0;i<n;i++)
       cin>>station[i];

2. Read the adjacent travel time between stations into matrix
T[i][j]
   for(int i=0;i<n;i++)
       for(j=0;j<n;j++)
           cin>>T[i][j];

If the stations are not adjacent then initialze the position value with 0

3. Read train stoppage time into S[i], Wait and Exit times of each station
   for(int i=0;i<n;i++){
       cin>>S[i];
       W[i]=S[i]/2;
       E[i]=S[i]/2;
   }
4. Enter Source & Destination Stations
   cin>>source>>dest;

5. Now match source and dest wth stations array
   int s,d;
   if(source==destination) quit;
   else
       for(int i=0;i<n;i++){
           if(strcmp(station[i],source)==0) s=i;
       }
       for(int i=0;i<n;i++){
           if(strcmp(station[i],dest)==0) d=i;
       }

6. Now create a temporary arrays with size nXn and initialize with -1;
   currDist[n];
   prevDist[n];
       for(int i=0;i<n;i++)
           currDist[i][j]=-1;
           prevDist[i]=-1;

   temp[0][0]=0;

7. Now find the distances from each vertex i to d (i !=d). Apply Disjkstra's shortest path algorithm now

   dist{s,d}=Minimum of{ distance between source "s" to its adjacent vertices + distance from adjacent vertex to 'd'}

   Find adjacent vertices to 's'
   vector<int> adjV; //adjacent Vertices to "s"
   int dist[n];

StepA:   for(int i=0;i<n;i++){
       if(T[s][i]!=0) {
           adjV.push_back(i);
           dist[i]=T[s][i];
       }
   }

StepB: for(int i=adjV[0];i<adjV.size();i++){
   if(T[i][d]!=0) then dist[i]+T[i][d];
      else
              {
       repeat stepA and stepB for this adjacent vertex and add that distance to dist
          }
   }

  

Now traverse the dist[] array and find the minimum value. That is the shortest path.
  
  

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.