Build path with pgr_dijkstra without shortcuts

[HardRock4Life]

Hi!

This is the result of the routing using pgr_dijkstra algorithm.

CREATE OR REPLACE FUNCTION public.nearest_id_v3(geom geometry)
 RETURNS bigint
 LANGUAGE sql
 STABLE PARALLEL SAFE STRICT
AS $function$
    SELECT node.id
    FROM public."Vertices" node
    JOIN public."Edges" edg
      ON (node.id = edg.source OR    -- Only return node that is
          node.id = edg.target)      --   an edge source or target.
    WHERE edg.source != edg.target   -- Drop circular edges.
    ORDER BY node.the_geom <-> $1    -- Find nearest node.
    LIMIT 1;
$function$
;

CREATE OR REPLACE FUNCTION postgisftw.find_route_dijkstra_v3(from_lon double precision, from_lat double precision, to_lon double precision , to_lat double precision)
 RETURNS TABLE(path_seq integer, edge bigint, cost double precision, agg_cost double precision, geom geometry)
 LANGUAGE plpgsql
 STABLE PARALLEL SAFE STRICT
AS $function$
    BEGIN
    RETURN QUERY
    WITH clicks AS (
	SELECT
        ST_SetSRID(ST_Point(from_lon, from_lat), 28992) AS start,
        ST_SetSRID(ST_Point(to_lon, to_lat), 28992) AS stop
    )
    SELECT dijk.path_seq, dijk.edge, dijk.cost, dijk.agg_cost, ways.geom
    FROM "Edges" ways
	cross join clicks
    JOIN pgr_dijkstra(
        'SELECT id, 
				source, 
				target, 
				st_length(geom) as cost, 
				geom FROM public."Edges"
		',
        -- source
        nearest_id_v3(clicks."start"),
        -- target
        nearest_id_v3(clicks.stop)
        ) AS dijk
        ON ways.id = dijk.edge;
    END;
$function$
;

The edges have been built manually, and the vertices are created using the function pgr_createTopology:

SELECT pgr_createTopology('edges', 4, the_geom := 'geom', clean:=true);

Why would algorithm build such a long path, what could be possible reasons?

PostgreSQL 13.3, compiled by Visual C++ build 1914, 64-bit

POSTGIS="3.1.2 3.1.2" [EXTENSION] PGSQL="130" GEOS="3.9.1-CAPI-1.14.1" PROJ="7.1.1" LIBXML="2.9.9" LIBJSON="0.12" LIBPROTOBUF="1.2.1" WAGYU="0.5.0 (Internal)"

PGRouting version: 3.2.0

P.S. I have built an algorithm which does not use pgr_createTopology, but builds it dynamically using points, interpolated from blue linestrings you see on a screenshot below.

The issue on this one has been posted at https://gis.stackexchange.com/questions/409136/pgrouting-build-path-without-shortcuts You can also find a code a had built for it there.

Thank you!

[cvvergara]

Your pgr_dijkstra is for a directed graph.

This is your query:

pgr_dijkstra(
        'SELECT id, 
				source, 
				target, 
				st_length(geom) as cost, --- There is no reverse_cost so there is no edge from target to source
				geom FROM public."Edges"
		',
        -- source
        nearest_id_v3(clicks."start"),
        -- target
        nearest_id_v3(clicks.stop) -- There is no directed flag set to false (aka undirected)
        ) AS dijk

The graph that is been built by the inner query and the flag visually speaking looks like the image bellow where I added arrows.
As you can not go using the wrong way, it will never give you the expected answer

Because of this instruction: st_length(geom) as cost, that normally is used for pedestrian applications.
In a pedestrian application the routing graph needed looks like in the next image where all segments are two way segments:

There are 2 ways to achive this routing graph:

Using reverse_cost

pgr_dijkstra(
        'SELECT id, 
				source, 
				target, 
				st_length(geom) as cost,
                                st_length(geom) as reverse_cost, --- Adding the segment that goes from target to source
				geom FROM public."Edges"
		',
        -- source
        nearest_id_v3(clicks."start"),
        -- target
        nearest_id_v3(clicks.stop) -- Still no directed flag set to false, but all reversed segments have been added
        ) AS dijk

Using directed flag

pgr_dijkstra(
        'SELECT id, 
				source, 
				target, 
				st_length(geom) as cost,  -- Not add the reversed segment
				geom FROM public."Edges"
		',
        -- source
        nearest_id_v3(clicks."start"),
        -- target
        nearest_id_v3(clicks.stop) 
        directed => false -- Use un-directed graph edges have no direction similar as having 2 way segments
        ) AS dijk

If the application is for cars do not use the length as cost and definitively you need a reverse column.
(I will move the issue to discussions)