Редактирование текущего веса ребра в графике

Я изучаю теорию графов. Я хочу редактировать текущий вес ребер.

Вот код

    #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;
}

Я ожидаю другого выхода, поскольку будет более короткий путь, если я изменил вес {«Фредериксбург», «Ричмонд»}, но повторное использование функции insertEdge не изменит вес значения. Как я могу редактировать вес ребер в реальном времени?

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector