CS 314 Assignment 10: Selected Answers



  1. Dijkstra's algorithm:
    Great-Circle Distance Austin to Muleshoe = 399
    
    start Dijkstra
    end Dijkstra, nodes = 63
    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 = 37
    Road Distance austin to muleshoe = 452
    Route to muleshoe = (austin lampasas brownwood abilene roscoe
                         snyder lubbock muleshoe)
    
    start A* randomlies
    end A*, nodes = 58                                                      [varies]
    Road Distance austin to muleshoe = 803                                  [varies]
    Route to muleshoe = (austin junction sonora san-angelo abilene haskell  [varies]
                         wichita-falls vernon plainview 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