Why are shortest paths sorted?

szhorvat · 13 February 2021 19:47

@Gabor Do you recall why the shortest paths obtained with Dijkstra are sorted? See here:

igraph/igraph/blob/develop/src/paths/dijkstra.c#L1051


            VECTOR(*res)[j] = path;
            j++;
        } else {
            /* we don't need this path, free it */
            igraph_vector_destroy(path); free(path);
        }
    }
    IGRAPH_CHECK(igraph_vector_ptr_resize(res, j));
    /* sort the paths by the target vertices */
    igraph_vector_ptr_sort(res, igraph_i_vector_tail_cmp);
}
/* free the allocated memory */
igraph_vector_destroy(&order);
igraph_Free(is_target);
igraph_vector_destroy(&dists);
igraph_vector_ptr_destroy_all(&parents);
IGRAPH_FINALLY_CLEAN(4);
return 0;

The unweighted version does not sort.

A Bellman-Ford version of the function was just added. Is there any reason to add the sorting to this new function?

Gabor · 13 February 2021 20:12

I guess: rigraph/structural.properties.R at a14fc50abf9bf3ae17b870ccbc21f88d0eefed6e · igraph/rigraph · GitHub

If the unweighted version does not, then it should, I guess, unless it is shorted in R.

Topic		Replies	Views
Longest path in a weighted DAG Usage R	4	852	31 July 2020
Will there be a significant improvement (>10 times speed) in shortest path calculation if using C instead of R version? Usage C , R	3	1913	30 January 2020
Transitivity calculation and node ordering Development C	4	417	10 May 2021
Question about how to get dfs() working ? Usage C , R	2	300	8 April 2023
How does random_edge_walk compute the probabilities in r-igraph? Usage R	2	280	17 August 2022

Why are shortest paths sorted?

Related Topics