#include <cstring>
    #include <iostream>
    #include "linked-list.h"
    using namespace std;

    // infinity means there is no path!
    const int INFINITY = 999999999;

    template <int N>
    class Graph {
      public:
        Graph( ) {
          count = 0;
        }

        // insert an edge (both directions)
        void insertEdge(const char fromcity[], const char tocity[], int cost) {
          int from = lookup(fromcity);
          int to = lookup(tocity);

          Edge e;
          e.to = to;
          e.cost = cost;
          nodes[from].edges.addAtEnd(e);
          e.to = from;
          nodes[to].edges.addAtEnd(e);
        }

        // return the cost of an edge or 0 for none
        int getCost(int from, int to) const {
          Edge e;
          e.to = to;
          e.cost = INFINITY;
          return nodes[from].edges.find(e).cost;
        }

        // add a node
        void insertNode(const char name[]) {
          strcpy(nodes[count].data, name);
          count++;
        }

        // return the node index of a city name
        int lookup(const char name[]) const {
          for(int i = 0; i < count; i++) {
            if(strcmp(nodes[i].data, name) == 0) {
              return i;
            }
          }

          return -1;
        }

        // return the name of a node index
        const char* name(int index) const {
          return nodes[index].data;
        }

      private:
        // an edge has a destination and cost
        struct Edge {
          int to, cost;

          bool operator==(const Edge& other) {
            return to == other.to;
          }
        };

        // a node has some data and a list of edges
        struct Node {
          char data[100];
          LinkedList<Edge> edges;
        };

        // the graph is an array of nodes
        Node nodes[N];
        int count;
    };

    // use Dijkstra's algorithm to find a shortest path
    template<int N>
    int shortestPath(const Graph<N>& graph, const char startcity[], const char endcity[]) {
      // find the city names indices
      int start = graph.lookup(startcity);
      int end = graph.lookup(endcity);

      // make an array of distances from start to the given node
      int tentative[N];

      // set all distances to infinity except start which is 0
      for(int i = 0; i < N; i++) {
        tentative[i] = INFINITY;
      }
      tentative[start] = 0;

      // make an array of which nodes we've seen
      bool visited[N];
      for(int i = 0; i < N; i++) {
        visited[i] = false;
      }

      // start at the start node
      int current = start;

      // loop until all nodes are visited
      while(current != -1) {
        cout << "Considering " << graph.name(current) << endl;
        // for each neighbor of current
        for(int i = 0; i < N; i++) {
          // if it's connected
          if(graph.getCost(current, i) < INFINITY) {
            // calculate the distance from start to i via current
            int distance = tentative[current] + graph.getCost(current, i);

            // if this distance is less than the tentative distance from start to i we have, replace it
            // also mark i as unvisited since we now have to reconsider it
            if(distance < tentative[i]) {
              cout << "Distance from " << graph.name(start) << " to " << graph.name(i) << " is " << distance << endl;
              tentative[i] = distance;
              visited[i] = false;
            }
          }
        }

        // mark current node as visited
        visited[current] = true;
        cout << endl;

        // set current node to unvisited one with the smallest cost
        int min = INFINITY;
        current = -1;
        for(int i = 0; i < N; i++) {
          if(!visited[i] && (tentative[i] < min)) {
            min = tentative[i];
            current = i;
          }
        }
      }

      // we now have the shortest path to ecery node in the graph
      // return the one we were interested in!
      return tentative[end];
    }

    int main( ) {
      // create a graph with the cities
      Graph<11> graph;
      graph.insertNode("Alexandria");
      graph.insertNode("Blacksburg");
      graph.insertNode("Charlottesville");
      graph.insertNode("Danville");
      graph.insertNode("Fredericksburg");
      graph.insertNode("Harrisonburg");
      graph.insertNode("Lynchburg");
      graph.insertNode("Newport News");
      graph.insertNode("Richmond");
      graph.insertNode("Roanoke");
      graph.insertNode("Virginia Beach");

      graph.insertEdge("Alexandria", "Fredericksburg", 50);
      graph.insertEdge("Fredericksburg", "Richmond", 60);
      graph.insertEdge("Richmond", "Charlottesville", 70);
      graph.insertEdge("Richmond", "Lynchburg", 110);
      graph.insertEdge("Richmond", "Danville", 145);
      graph.insertEdge("Richmond", "Newport News", 70);
      graph.insertEdge("Newport News", "Virginia Beach", 35);
      graph.insertEdge("Virginia Beach", "Danville", 210);
      graph.insertEdge("Danville", "Lynchburg", 70);
      graph.insertEdge("Lynchburg", "Charlottesville", 70);
      graph.insertEdge("Lynchburg", "Roanoke", 65);
      graph.insertEdge("Roanoke", "Blacksburg", 40);
      graph.insertEdge("Blacksburg", "Harrisonburg", 140);
      graph.insertEdge("Harrisonburg", "Alexandria", 135);
      graph.insertEdge("Harrisonburg", "Charlottesville", 50);

      cout << endl << "Distance is " << shortestPath(graph, "Alexandria", "Danville") << endl;
   graph.insertEdge("Fredericksburg", "Richmond", 40);  //<-- attempt at changing the value from 60 to 40//
     cout << endl << "Distance is " << shortestPath(graph, "Alexandria", "Danville") << endl;// the output is still the same,and the edge weight did not change//

      return 0;
    }