projects
/
mtp.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
431a713
)
Prevent the same vertex to be added twice to the front in find_shortest_path.
author
Francois Fleuret
<francois@fleuret.org>
Tue, 21 Aug 2012 21:59:49 +0000
(14:59 -0700)
committer
Francois Fleuret
<francois@fleuret.org>
Tue, 21 Aug 2012 21:59:49 +0000
(14:59 -0700)
mtp.cc
patch
|
blob
|
history
diff --git
a/mtp.cc
b/mtp.cc
index
a9388f6
..
b400650
100644
(file)
--- a/
mtp.cc
+++ b/
mtp.cc
@@
-56,11
+56,9
@@
public:
class Vertex {
public:
class Vertex {
public:
- int id;
-
+ int id, iteration;
Edge *root_edge;
scalar_t distance_from_source;
Edge *root_edge;
scalar_t distance_from_source;
-
Vertex *pred_vertex;
Edge *pred_edge;
Vertex *pred_vertex;
Edge *pred_edge;
@@
-89,7
+87,6
@@
class Graph {
Edge *edge_heap;
Vertex *vertices;
Vertex *source, *sink;
Edge *edge_heap;
Vertex *vertices;
Vertex *source, *sink;
-
public:
Graph(int nb_vertices, int nb_edges, int *from, int *to, scalar_t *lengths,
int source, int sink);
public:
Graph(int nb_vertices, int nb_edges, int *from, int *to, scalar_t *lengths,
int source, int sink);
@@
-174,7
+171,7
@@
void Graph::find_shortest_path(Vertex **front, Vertex **new_front) {
for(int n = 0; n < nb_vertices; n++) {
for(Edge *e = vertices[n].root_edge; e; e = e->next) {
if(e->work_length < 0) {
for(int n = 0; n < nb_vertices; n++) {
for(Edge *e = vertices[n].root_edge; e; e = e->next) {
if(e->work_length < 0) {
- cerr << "DEBUG error in find_shortest_path: Edge
fixed
lengths have to be positive."
+ cerr << "DEBUG error in find_shortest_path: Edge
work
lengths have to be positive."
<< endl;
abort();
}
<< endl;
abort();
}
@@
-186,14
+183,18
@@
void Graph::find_shortest_path(Vertex **front, Vertex **new_front) {
vertices[v].distance_from_source = FLT_MAX;
vertices[v].pred_vertex = 0;
vertices[v].pred_edge = 0;
vertices[v].distance_from_source = FLT_MAX;
vertices[v].pred_vertex = 0;
vertices[v].pred_edge = 0;
+ vertices[v].iteration = 0;
}
}
+ int iteration = 0;
+
int front_size = 0, new_front_size;
front[front_size++] = source;
source->distance_from_source = 0;
do {
new_front_size = 0;
int front_size = 0, new_front_size;
front[front_size++] = source;
source->distance_from_source = 0;
do {
new_front_size = 0;
+ iteration++;
for(int f = 0; f < front_size; f++) {
v = front[f];
for(Edge *e = v->root_edge; e; e = e->next) {
for(int f = 0; f < front_size; f++) {
v = front[f];
for(Edge *e = v->root_edge; e; e = e->next) {
@@
-203,7
+204,10
@@
void Graph::find_shortest_path(Vertex **front, Vertex **new_front) {
tv->distance_from_source = d;
tv->pred_vertex = v;
tv->pred_edge = e;
tv->distance_from_source = d;
tv->pred_vertex = v;
tv->pred_edge = e;
- new_front[new_front_size++] = tv;
+ if(tv->iteration < iteration) {
+ new_front[new_front_size++] = tv;
+ tv->iteration = iteration;
+ }
}
}
}
}
}
}