void MainWindow shortest_route clear_graph for int nodes size for int

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
void MainWindow::shortest_route()
{
clear_graph();
for (int i=0; i<nodes.size(); i++)
{
for(int j=0; j<nodes[i].second->edges.size(); j++)
{
((Edge*)(nodes[i].second->edges[j]))->show_length=true;
((Edge*)(nodes[i].second->edges[j]))->update();
}
}
std::vector<std::pair<std::vector<Node*>,int> > pathnodes;
std::vector<std::pair<std::vector<Edge*>,int> > pathedges;
for (int i=0; i<this->nodes.size(); i++)
{
std::vector<Edge*> foundedges;
std::vector<Node*> foundnodes;
find_shortest_route(nodes[i].second,
&pathnodes, &pathedges,
foundedges,
foundnodes, 0, 0);
}
int min=1<<30;
for (int i=0; i< pathnodes.size(); i++)
{
if (pathnodes[i].second<min) min=pathnodes[i].second;
}
for(int i=pathnodes.size(); i>0; i--)
{
if (pathnodes[i].second==min)
{
for (int j=0; j<pathnodes[i].first.size();j++)
{
pathnodes[i].first[j]->mark+=" "+QString(j+49);
pathnodes[i].first[j]->color=Qt::blue;
pathnodes[i].first[j]->update();
}
int shortest_route_count=0;
for (int j=0; j<pathnodes.size();j++)
{
if (pathnodes[j].second==min) shortest_route_count++;
}
if (shortest_route_count>1)
{
show_message(
QString("Довжина шляху: ")
+ QString::number(min)
+QString("\nIнших шляхiв\nтакої ж довжини: ")
+ QString(shortest_route_count+48));
}
break;
}
}
}
void MainWindow::find_shortest_route(Node* node,
std::vector<std::pair<std::vector<Node*>,int> > *r_nodes,
std::vector<std::pair<std::vector<Edge*>,int> > *r_edges,
std::vector<Edge*> v_edges,
std::vector<Node*> v_nodes, int len, int count)
{
int min=1<<30;
for(int i=0; i<r_nodes->size(); i++)
{
if ((*r_nodes)[i].second<min) min = (*r_nodes)[i].second;
}
if (len>min) return;
v_nodes.push_back(node);
count++;
int visited=0;
if (count>(nodes.size()*(nodes.size()-1))) return;
//printf("%d %d\n", len, count);
for(int i=0; i<nodes.size(); i++)
{
for(int j=0; j<v_nodes.size(); j++)
{
if (v_nodes[j]==nodes[i].second)
{
visited++;
break;
}
}
}
if (visited == nodes.size())
{
(*r_nodes).push_back(std::make_pair(v_nodes,len));
(*r_edges).push_back(std::make_pair(v_edges,len));
return;
}
for (int i=0; i< node->edges.size(); i++)
{
v_edges.push_back((Edge*)(node->edges[i]));
if ((len+((Edge*)(node->edges[i]))->length)<min)
{
if (((Edge*)node->edges[i])->one==node)
{
find_shortest_route(((Edge*)node->edges[i])->two, r_nodes, r_edges,
v_edges, v_nodes,
len+((Edge*)node->edges[i])->length, count);
}
else if (((Edge*)node->edges[i])->two==node)
{
find_shortest_route(((Edge*)node->edges[i])->one, r_nodes, r_edges,
v_edges, v_nodes,
len+((Edge*)node->edges[i])->length, count);
}
}
}
}