From 7eeb29220a73ab9c5367f652873042f8a81c6cef Mon Sep 17 00:00:00 2001 From: Jingrong Chen Date: Mon, 22 Jan 2024 18:13:01 -0500 Subject: [PATCH] Fix bug in shortest path implementation --- src/graph.c | 6 ++++-- src/node.h | 1 + 2 files changed, 5 insertions(+), 2 deletions(-) diff --git a/src/graph.c b/src/graph.c index 5a7a16a7..5bec2c16 100644 --- a/src/graph.c +++ b/src/graph.c @@ -141,6 +141,7 @@ void sssp_bfs(void) { myself->prevedge = NULL; myself->via = myself; myself->distance = 0; + myself->weighted_distance = 0; list_insert_head(todo_list, myself); /* Loop while todo_list is filled */ @@ -178,14 +179,15 @@ void sssp_bfs(void) { if(e->to->status.visited && (!e->to->status.indirect || indirect) - && (e->to->distance != n->distance + 1 || e->weight >= e->to->prevedge->weight)) { + && (e->to->distance != n->distance + 1 || e->to->weighted_distance <= n->weighted_distance + e->weight)) { continue; } // Only update nexthop if it doesn't increase the path length - if(!e->to->status.visited || (e->to->distance == n->distance + 1 && e->weight < e->to->prevedge->weight)) { + if(!e->to->status.visited || (e->to->distance == n->distance + 1 && e->to->weighted_distance > n->weighted_distance + e->weight)) { e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop; + e->to->weighted_distance = n->weighted_distance + e->weight; } e->to->status.visited = true; diff --git a/src/node.h b/src/node.h index 51322c25..7d5a0c8c 100644 --- a/src/node.h +++ b/src/node.h @@ -76,6 +76,7 @@ typedef struct node_t { compression_level_t outcompression; /* Compression level, 0 = no compression */ int distance; + int weighted_distance; struct node_t *nexthop; /* nearest node from us to him */ struct edge_t *prevedge; /* nearest node from him to us */ struct node_t *via; /* next hop for UDP packets */ -- 2.20.1