UAB – 2005: Problem 6: Shortest Path in Alabama


Write a program to find the shortest routing and distance between two Alabama cities using the following distance table.

You are not allowed to use any other manually computed distances in your program.

Alabaster-Birmingham 24 miles
Alabaster-Montgomery 71 miles
Birmingham-Huntsville 103 miles
Birmingham-Tuscaloosa 59 miles
Demopolis-Mobile 141 miles
Demopolis-Montgomery 101 miles
Demopolis-Tuscaloosa 65 miles
Mobile-Montgomery 169 miles
Montgomery-Tuscaloosa 134 miles

Example 1:
Enter city #1: Demopolis
Enter city #2: Birmingham
Shortest routing and distance:
Demopolis-Tuscaloosa-Birmingham, 124 miles

Example 2:
Enter city #1: Mobile
Enter city #2: Huntsville
Shortest routing and distance: Mobile-Montgomery-Alabaster-Birmingham-Huntsville, 367 miles


Enter city #1: Tuscaloosa
Enter city #2: Alabaster
Shortest routing and distance:
Tuscaloosa-Birmingham-Alabaster, 83 miles

Enter city #1: Demopolis
Enter city #2: Mobile
Shortest routing and distance:
Demopolis-Mobile, 141 miles

Enter city #1: Huntsville
Enter city #2: Birmingham
Shortest routing and distance:
Huntsville-Birmingham, 103 miles

Enter city #1: Demopolis
Enter city #2: Alabaster
Shortest routing and distance:
Demopolis-Tuscaloosa-Birmingham-Alabaster, 148 miles

Enter city #1: Alabaster
Enter city #2: Demopolis
Shortest routing and distance:
Alabaster-Birmingham-Tuscaloosa-Demopolis, 148 miles


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <string>
#include <iostream>
#include <vector>

#define Alabaster   "Alabaster"
#define Birmingham  "Birmingham"
#define Demopolis   "Demopolis"
#define Mobile      "Mobile"
#define Montgomery  "Montgomery"
#define Huntsville  "Huntsville"
#define Tuscaloosa  "Tuscaloosa"

using namespace std;

struct node {
    string sourceCity;
    string destinationCity;
    int miles;
    
    node () {}
    
    node (string sourceCity, string destinationCity, int miles) {
        this->sourceCity = sourceCity;
        this->destinationCity = destinationCity;
        this->miles = miles;
    };
    
} routing [9];

void populateData()
{
    routing [0] = node (Alabaster, Birmingham, 24);
    routing [1] = node (Alabaster, Montgomery, 71);
    routing [2] = node (Birmingham, Huntsville, 103);
    routing [3] = node (Birmingham, Tuscaloosa, 59);
    routing [4] = node (Demopolis, Mobile, 141);
    routing [5] = node (Demopolis, Montgomery, 101);
    routing [6] = node (Demopolis, Tuscaloosa, 65);
    routing [7] = node (Mobile, Montgomery, 169);
    routing [8] = node (Montgomery, Tuscaloosa, 134);
}

// best path among all the paths
vector <string> bestPath;

// best cost among all the acceptable cost
int bestCost;

// intermediate path
vector <string> path;

// user input, source and destination city 
string city1, city2;

// check if the cityName is already visited 
bool notInPath(string cityName)
{
    for ( int i = 0; i < path.size(); i++ ) {
        if ( path [i] == cityName ) return false;
    }
    
    return true;
}

void recurShortestPath(string currentCity, int currentCost)
{
    if (currentCity == city2) {
        if (currentCost < bestCost) {
            bestCost = currentCost;
            bestPath = path;
        }
        return;
    }
    
    // loop through all the routing paths 
    for ( int i = 0; i < 9; i++ ) {
        if (routing [i].sourceCity == currentCity && notInPath(routing [i].destinationCity)) {
            // put the next city in the path 
            path.push_back(routing [i].destinationCity);
            // lets do the experiment
            recurShortestPath(routing [i].destinationCity, currentCost + routing [i].miles);
            // preserve the previous state 
            path.pop_back();
            
        } else if (routing [i].destinationCity == currentCity && notInPath(routing [i].sourceCity)) {
            path.push_back(routing [i].sourceCity);
            recurShortestPath(routing [i].sourceCity, currentCost + routing [i].miles);
            path.pop_back();
        }
    }
}

int main (int argc, char *argv [])
{
    populateData();

    // initially bestCost is the maximum value ever
    bestCost = INT_MAX;
    
    printf ("Enter city #1: ");
    cin >> city1;
    
    printf("Enter city #2: ");
    cin >> city2;
    
    path.push_back(city1);
    
    recurShortestPath(city1, 0);
    
    printf ("Shortest routing and distance:\n");
    bool isHyphen = false;
    
    for ( int i = 0; i < bestPath.size(); i++ ) {
        if (isHyphen) printf ("-");
        isHyphen = true;
        
        cout << bestPath [i];
    }
    
    printf (", %d miles\n", bestCost);
    
    return 0;
}

// @END_OF_SOURCE_CODE

3 thoughts on “UAB – 2005: Problem 6: Shortest Path in Alabama

  1. I have a little bit of trouble with understanding the solution. Why the vector header file is included here?

  2. this is a sample program that will only return an output if “Mobile” and “Alabaster” are the inputs. The order in which they are entered doesnt matter.

    #include
    #include
    int main(){
    char city1[11];
    char city2[11];
    int i;
    printf(“please enter the name of the first city: “);
    fgets(city1,11,stdin);
    for(i=0;i<11;i++){
    if(city1[i]=='\n'){
    city1[i]='\0';
    }
    }
    printf("\n");
    printf("please enter the name of the second city: ");
    fgets(city2,11,stdin);
    for(i=0;i<11;i++){
    if(city2[i]=='\n'){
    city2[i]='\0';
    }
    }
    printf("\n");
    if(strcmp(city1,"Alabaster")==0&&strcmp(city2,"Mobile")==0){
    printf("the shortest routing and distance: Alabaster-Montgomery-Mobile, 193 miles.\n");
    }
    else if(strcmp(city1,"Mobile")==0&&strcmp(city2,"Alabaster")==0){
    printf("the shortest routing and distance: Mobile-Montgomery-Alabaster, 193 miles.\n");
    }
    printf("\n");
    return 0;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s