-
- logger(DEBUG_SCARY_THINGS, LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name,
- e->to->name, e->weight);
- }
-}
-
-/* Implementation of Dijkstra's algorithm.
- Running time: O(N^2)
-*/
-
-static void sssp_dijkstra(void) {
- splay_node_t *node, *to;
- edge_t *e;
- node_t *n, *m;
- list_t *todo_list;
- list_node_t *lnode, *nnode;
- bool indirect;
-
- todo_list = list_alloc(NULL);
-
- logger(DEBUG_SCARY_THINGS, LOG_DEBUG, "Running Dijkstra's algorithm:");
-
- /* Clear visited status on nodes */
-
- for(node = node_tree->head; node; node = node->next) {
- n = node->data;
- n->status.visited = false;
- n->status.indirect = true;
- n->distance = -1;
- }
-
- /* Begin with myself */
-
- myself->status.indirect = false;
- myself->nexthop = myself;
- myself->via = myself;
- myself->distance = 0;
- list_insert_head(todo_list, myself);
-
- /* Loop while todo_list is filled */
-
- while(todo_list->head) {
- n = NULL;
- nnode = NULL;
-
- /* Select node from todo_list with smallest distance */
-
- for(lnode = todo_list->head; lnode; lnode = lnode->next) {
- m = lnode->data;
- if(!n || m->status.indirect < n->status.indirect || m->distance < n->distance) {
- n = m;
- nnode = lnode;
- }