CS 314 Assignment 10: Selected Answers



  1. Dijkstra's algorithm:
    Great-Circle Distance Austin to Muleshoe = 399
    
    start Dijkstra
    end Dijkstra, nodes = 71
    Road Distance austin to muleshoe = 452
    Route to muleshoe = (austin lampasas brownwood abilene roscoe
                         snyder lubbock muleshoe)
    

  2. A* algorithm:
    
    start A* dist
    end A*, nodes = 11
    Road Distance austin to muleshoe = 452
    Route to muleshoe = (austin lampasas brownwood abilene roscoe
                         snyder lubbock muleshoe)
    
    
    start A* halfass
    end A*, nodes = 40
    Road Distance austin to muleshoe = 452
    Route to muleshoe = (austin lampasas brownwood abilene roscoe
                         snyder lubbock muleshoe)
    
    start A* randomlies
    end A*, nodes = 31                                            [varies]
    Road Distance austin to muleshoe = 812                        [varies]
    Route to muleshoe = (austin junction sonora van-horn pecos    [varies]
                         odessa seminole lubbock muleshoe)
    

  3. Prim's algorithm:
    
    start Prim
    end Prim, total cost = 3598
    edgecost austin to temple = 62
    Route Austin to Muleshoe = (austin lampasas brownwood abilene roscoe
                                big-spring lamesa lubbock muleshoe)
    pathcost austin to muleshoe = 501
    Total cost of all roads = 8061