UAB – 2005: Problem 6: Shortest Path in Alabama

Posted on by Shahab

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

Published by Shahab

Completed B.Sc in CSE, @United International University, Dhaka. Currently working as Development Engineer, Android and iOS Application.

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. A JS-solution:


    /*
    JS-solution to:
    https://tausiq.wordpress.com/2013/08/08/uab-2005-problem-6-shortest-path-in-alabama/
    */
    var getRoutes = (function(){
    var rawData = [
    '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'
    ];
    // transform raw data into towns and distances
    var towns = [], dists = [];
    rawData.forEach(function(x){
    x = x.split(' ');
    var y = x[0].split('-');
    towns.indexOf(y[0]) < 0 && towns.push(y[0]);
    towns.indexOf(y[1]) < 0 && towns.push(y[1]);
    dists.push([y[1],y[0],x[1]/1]);
    dists.push([y[0],y[1],x[1]/1]);
    });
    towns = towns.sort();
    window.towns = towns; // export just for test gui
    // find all routes
    var routes = [], routemem = towns.slice(), routemem2, one;
    // add zero distance routes (to-from same city)
    towns.forEach(function(town){
    routes.push([0,town,town]);
    });
    // add all other routes
    do {
    routemem2 = [];
    towns.forEach(function(town){
    routemem.forEach(function(route){
    route = route.push ? route : [route];
    dists.forEach(function(dist){
    if(
    dist[0] == route[route.length-1] &&
    dist[1] == town &&
    route.indexOf(town) < 0
    ){
    one = route.concat(town);
    if(one[0]/1 != one[0]){one.unshift(0);}
    one[0] += dist[2];
    routemem2.push(one);
    }
    });
    });
    });
    routemem = routemem2;
    routes = routes.concat(routemem);
    } while (routemem2.length);
    // order routes (shortest to longest)
    routes.sort(function(x,y){
    return x[0] < y[0] ? -1 : 1;
    });
    // get all routes between two cities (shortest first)
    return function(from,to){
    return routes.filter(function(x){
    return x[1] == from && x[x.length-1] == to;
    }).map(function(x){
    x = x.slice();
    var miles = x.shift();
    return {route:x.join('-'),distance:miles + ' miles'};
    });
    }
    })();
    // Small GUI to test the solution
    var selects = ' from <select id="from"><option value="">-</option>';
    towns.forEach(function(town){
    selects += '<option value="' + town + '">' + town + '</opton>';
    });
    selects += '</select>';
    selects += selects.split('from').join('to');
    html = '<h1>Route planner</h1><p>Travel ' + selects +
    '</p><p id="result"></p>';
    document.write(html);
    function d(x){return document.getElementById(x);}
    var from = d('from'), to = d('to'), result = d('result');
    [from,to].forEach(function(x){
    x.addEventListener('change',showResult);
    });
    function showResult(){
    var r = getRoutes(from.value,to.value).map(function(x){
    return '<span style="display:inline-block;width:600px">' +
    x.route + '</span>' + x.distance;
    });
    r.length && r.unshift('<strong>Shortest route:</strong>');
    r.length>2 && r.splice(2,0,"<br><strong>Other routes:</strong>");
    result.innerHTML = r.join("<br>");
    }

    view raw

    routes_in_alabama.js

    hosted with ❤ by GitHub

  3. 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 comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.