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
Shortest paths weights in C Usage C	3	708	8 June 2021
topo_sort() algorithm Usage R	5	681	5 August 2021
Unexpected shortest path for weighted graph Usage Python	2	206	9 August 2023
TODO in unweighted shortest path implementations (BFS)? Development C	2	468	3 March 2020
igraph_distances_dijkstra Usage C	2	123	4 March 2024

Why are shortest paths sorted?

Related topics