Weighted Graphs and Shortest Paths in NebulaGraph with C#, Part 5

If you give a traveller the shortest path from Stockholm to San Francisco by hop count, you might send them through two hubs with a combined fare of $2,400, while a three hop route through different hubs costs $480. NebulaGraph's FIND SHORTEST PATH will happily return the expensive two hop route, because it is BFS based and knows nothing about edge weights. That gap is what this article is about.

This is Part 5 of the series. Part 1 covered the NebulaGraph data model and the C# client. Now we put weight on the edges and build a traversal layer that understands cost.

When Edges Carry Weight

Not every relationship is equal. In a plain hop graph every edge costs 1. In a real system edges carry a cost that belongs to the domain:

• Distance. Kilometres between airports, or latency between microservices.
• Time. Flight duration, queue wait, propagation delay.
• Price. Ticket fare, licence cost, compute spend.
• Affinity. The inverse of a similarity score in a recommendation graph.

Which weight you minimise changes the answer completely. The cheapest route is not the fastest one. If you model all of them as separate properties on one edge type, you can switch objective without touching the schema.

Modeling the Flight Network

The schema uses an airport tag and a route edge type. The edge carries all three weights at once. There is no reason to split them into separate edge types.

// Schema DDL expressed as nGQL constants in C#, run once at startup
public static class FlightSchema
{
    public const string CreateAirportTag = """
        CREATE TAG IF NOT EXISTS airport(
            code   STRING NOT NULL,
            city   STRING NOT NULL
        );
        """;
 
    public const string CreateRouteEdge = """
        CREATE EDGE IF NOT EXISTS route(
            distance_km  INT    NOT NULL,
            duration_min INT    NOT NULL,
            price        DOUBLE NOT NULL
        );
        """;
 
    // VID convention: 'ap:' prefix keeps airport vertices namespaced
    public static string Vid(string iataCode) => $"ap:{iataCode}";
}

Vertices use string VIDs in the ap:<IATA> pattern, which is the idiomatic NebulaGraph style. Since v3.3.0 every vertex must carry at least one tag, so always attach airport when you insert, or the write is rejected.

Inserting a pair of airports and a route looks like this:

INSERT VERTEX airport(code, city) VALUES 'ap:ARN':('ARN','Stockholm'), 'ap:SFO':('SFO','San Francisco');
INSERT EDGE route(distance_km, duration_min, price)
    VALUES 'ap:ARN'->'ap:LHR':(1819, 150, 210.00);

Shortest Path in NebulaGraph, and the Hop Versus Weight Problem

NebulaGraph (v3.8.x OSS, v5.x Enterprise) gives you three path finding statements:

FIND SHORTEST PATH FROM 'ap:ARN' TO 'ap:SFO' OVER route UPTO 5 STEPS YIELD path
FIND ALL PATH       FROM 'ap:ARN' TO 'ap:SFO' OVER route UPTO 4 STEPS YIELD path
FIND NOLOOP PATH    FROM 'ap:ARN' TO 'ap:SFO' OVER route UPTO 4 STEPS YIELD path

FIND SHORTEST PATH runs a bidirectional BFS. BFS walks the graph level by level, so the first time it reaches the destination it has the route with the fewest hops. It never reads price, duration_min or any other edge property. Those fields are simply invisible to the algorithm.

This is not a bug, it is what BFS does. The trouble is that people who have not worked with graph internals assume "shortest" means cheapest or fastest. It means fewest hops.

Neo4j (GDS Dijkstra) and Memgraph (*WSHORTEST (r, n | r.weight)) implement weighted shortest path in the engine. NebulaGraph 3.x Community does not have a weight property clause. The pattern that works here is:

1. Enumerate the bounded paths with FIND ALL PATH ... UPTO N STEPS.
2. Return the path list to C#.
3. Reduce on the weight you care about with LINQ or a priority queue.

That is not a hack. It is a clean line between the database and your code. The graph engine handles topology, your application owns the objective.

Cost Aware Traversal: Enumerate, Sum, Pick the Minimum

Dijkstra's algorithm walks nodes in order of cumulative cost using a min heap. If you already have a bounded set of paths in memory, you do not need the full algorithm. A single MinBy over the list does the same job for small result sets. For larger ones, a real priority queue saves allocations. There is more on that in the performance section.

The idea maps straight onto the LeetCode "cheapest flights within K stops" problem. UPTO N STEPS in nGQL is the K constraint on the Dijkstra state space. UPTO 4 STEPS means at most four edges, so three intermediate airports.

public record Hop(string FromVid, string ToVid, int DistanceKm, int DurationMin, double Price);
 
public record Route(IReadOnlyList<Hop> Hops, double TotalPrice, int TotalDurationMin)
{
    public string Summary =>
        string.Join(" > ", Hops.Select(h => h.FromVid.Replace("ap:", "")))
        + " > " + Hops[^1].ToVid.Replace("ap:", "");
}

The Route record holds the ordered list of hops plus the totals, computed once. Path results come back from NebulaGraph as alternating vertex and edge sequences in the ResultSet, so rebuilding them is explicit.

Returning a Path to C#: FindCheapestRouteAsync

This method runs FIND ALL PATH, turns each path into a Route, and returns the cheapest one by price.

public sealed class FlightRouteService
{
    private readonly INebulaSession _session;
 
    public FlightRouteService(INebulaSession session) => _session = session;
 
    public async Task<Route?> FindCheapestRouteAsync(
        string originCode,
        string destCode,
        int maxStops = 3,          // UPTO maxStops+1 STEPS
        CancellationToken ct = default)
    {
        // Keep the hop limit conservative, combinatorial growth is real
        int maxSteps = Math.Min(maxStops + 1, 5);
 
        string nGQL = $"""
            FIND ALL PATH FROM '{FlightSchema.Vid(originCode)}'
                          TO   '{FlightSchema.Vid(destCode)}'
                          OVER route
                          UPTO {maxSteps} STEPS
                          YIELD path
            """;
 
        var result = await _session.ExecuteAsync(nGQL, ct);
        if (!result.IsSucceeded)
            throw new InvalidOperationException($"NebulaGraph error: {result.GetErrorMessage()}");
 
        var routes = new List<Route>();
 
        foreach (var row in result.AsEnumerable())
        {
            var path   = row["path"].AsPath();       // NebulaGraph client path type
            var hops   = new List<Hop>();
            var nodes  = path.GetNodes();
            var rels   = path.GetRelationships();
 
            for (int i = 0; i < rels.Count; i++)
            {
                var rel = rels[i];
                hops.Add(new Hop(
                    FromVid:     nodes[i].GetId().AsString(),
                    ToVid:       nodes[i + 1].GetId().AsString(),
                    DistanceKm:  (int)rel.Properties["distance_km"].AsLong(),
                    DurationMin: (int)rel.Properties["duration_min"].AsLong(),
                    Price:       rel.Properties["price"].AsDouble()
                ));
            }
 
            routes.Add(new Route(
                Hops:           hops,
                TotalPrice:     hops.Sum(h => h.Price),
                TotalDurationMin: hops.Sum(h => h.DurationMin)
            ));
        }
 
        // Pick the cheapest. Swap the MinBy selector to optimise for duration instead
        return routes.Count == 0 ? null : routes.MinBy(r => r.TotalPrice);
    }
}

Going from cheapest to fastest is a one word change: replace r.TotalPrice with r.TotalDurationMin. The query does not change at all. That is the payoff of keeping the objective in C#.

If your result set is large before filtering, use the Dijkstra style priority queue instead. System.Collections.Generic.PriorityQueue<TElement, TPriority> has been in the BCL since .NET 6. Enqueue each partial path by cumulative cost and drop anything already worse than the best known route.

Performance Considerations

Hop Limits and Combinatorial Growth

FIND ALL PATH grows as O(b^d), where b is the average branching factor and d is the depth. A hub heavy flight graph with 50 outbound routes per major airport at UPTO 5 STEPS can return tens of thousands of paths. In practice:

• Keep UPTO N at 4 or below for production queries with no cache in front. Five steps on a dense graph is a timeout waiting to happen.
• Filter on edge properties before expanding where you can. NebulaGraph allows WHERE on edge properties in GO traversals, so using GO to narrow candidates and FIND ALL PATH for the final routes is a reasonable two phase pattern.
• Do not let the user set maxStops directly. Clamp it on the server.

Precomputing Hot Origin and Destination Pairs

In a flight search product the top 200 origin and destination pairs by volume cover most of the traffic. Precompute those on a schedule, nightly or whenever the flight data changes, and write the results into a cache, either Redis or a materialised cheapest_route edge type in the graph itself. At query time check the cache before you touch FIND ALL PATH.

Thread Configuration

num_operator_threads in nebula-graphd.conf controls how much parallelism path finding gets. The valid range is 2 to 10, and it must not be higher than the CPU core count of the graphd host. Do not set it to 10 on a 4 core VM, you will make throughput worse.

Key Takeaways

Weighted shortest path in NebulaGraph is a two layer problem. The graph engine owns topology and finds every structurally valid path inside your hop budget. C# owns the objective and picks the best path by price, duration or distance. That split is deliberate in NebulaGraph's architecture, and it fits the way .NET services are usually built anyway.

The next part of the series looks at graph projections and subgraph extraction, which is how you pull a filtered view of the graph into memory for analytics in process.