Weighted Graphs & Shortest Paths in NebulaGraph with C# — Part 5

If you hand a traveler the shortest path from Stockholm to San Francisco by hop count, you might route them through two hubs with a combined airfare of $2,400. The three-hop itinerary via different hubs costs $480. NebulaGraph's FIND SHORTEST PATH would cheerfully return the expensive two-hop path — because it is BFS-based and knows nothing about edge weights. That mismatch is the central problem this article solves.

This is Part 5 of the series. Part 1 introduced NebulaGraph's data model and the C# client. We now add weight to edges and build a cost-aware traversal layer.

When Edges Carry Weight

Not all relationships are equal. In a pure hop graph, every edge costs 1. In real systems edges carry domain-specific costs:

• Distance — kilometres between airports, or latency between microservices.
• Time — flight duration, queue wait, propagation delay.
• Price — ticket fare, licensing cost, compute spend.
• Affinity — inverse similarity score in recommendation graphs.

The choice of which weight to minimize changes the answer entirely. A route optimized for price differs from one optimized for duration. Modeling these as separate properties on a single edge type lets you switch objective functions without changing the schema.

Modeling the Flight Network

Our running schema uses a airport tag and a route edge type. The edge carries all three weights simultaneously — there is no architectural 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 — idiomatic NebulaGraph. Since v3.3.0, every vertex must carry at least one tag; always attach airport when inserting, or the write will be rejected.

Inserting a pair of airports and a route looks like:

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 — The Hop-vs-Weight Caveat

NebulaGraph (v3.8.x OSS, v5.x Enterprise) provides three path-finding variants:

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 uses a bidirectional BFS strategy. BFS explores edges level by level; the first time it reaches the destination it has found the fewest-hop route. It never reads price, duration_min, or any other edge property — those fields are invisible to the path algorithm.

This is not a bug; it is the documented behaviour of BFS. The problem is that developers unfamiliar with graph internals assume "shortest" means cheapest or fastest. It means fewest hops.

Databases like Neo4j (GDS Dijkstra) and Memgraph (*WSHORTEST (r, n | r.weight)) implement weighted shortest path natively. NebulaGraph 3.x Community does not expose a weight-property clause. The correct pattern for NebulaGraph is:

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

This is not a workaround — it is a clean DB/compute boundary. The graph engine handles topology traversal; your application layer owns the optimization objective.

Cost-Aware Traversal: Enumerate, Sum, Pick the Min

Dijkstra's algorithm processes nodes in order of cumulative cost using a min-heap. When you already have a bounded set of paths in memory, you do not need the full algorithm — a single MinBy over the path list is equivalent for small result sets. For large result sets (see the performance section), a proper priority queue reduces allocations.

The key insight maps directly to the LeetCode "cheapest flights within K stops" pattern: UPTO N STEPS in nGQL is the K constraint on the Dijkstra state space. Setting UPTO 4 STEPS means at most 4 edges traversed — 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 captures the full ordered sequence of hops plus pre-computed aggregates. Because path results from NebulaGraph arrive as alternating vertex/edge sequences in the ResultSet, reconstruction is explicit.

Returning a Path to C#: FindCheapestRouteAsync

The method below issues FIND ALL PATH, parses each path into a Route, then returns the cheapest 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 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 .MinBy selector to optimize for duration instead
        return routes.Count == 0 ? null : routes.MinBy(r => r.TotalPrice);
    }
}

Switching from price-optimal to time-optimal is a one-word change: replace r.TotalPrice with r.TotalDurationMin. The graph query stays identical. That is the payoff of keeping the optimization logic in C#.

For callers that want the Dijkstra priority-queue approach (useful when result sets are large before filtering), System.Collections.Generic.PriorityQueue<TElement, TPriority> — available since .NET 6 — is the idiomatic choice. Enqueue each partial path by cumulative cost and skip paths that exceed the known best.

Performance Considerations

Hop Limits and Combinatorial Blow-Up

FIND ALL PATH growth is 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. Concrete guidance:

• Keep UPTO N at 4 or below for production queries without caching. Five steps on a dense graph is a timeout waiting to happen.
• Pre-filter on edge properties before path expansion where possible. NebulaGraph allows WHERE clauses on edge properties in GO traversals; combining GO for candidate filtering with FIND ALL PATH for final routes is a valid two-phase pattern.
• Avoid exposing raw maxStops as a user-controlled parameter. Clamp it server-side.

Precomputing Hot Origin-Destination Pairs

For a flight search product, the top 200 origin-destination pairs by volume cover the majority of queries. Precompute those routes on a schedule (nightly or on flight data changes) and write the results into a cache (Redis, or a materialized cheapest_route edge type in the graph itself). At query time, check the cache before hitting FIND ALL PATH.

Thread Configuration

NebulaGraph's num_operator_threads setting in nebula-graphd.conf controls path-finding parallelism. The valid range is 2–10 and must not exceed the CPU core count of the graphd host. Do not blindly set it to 10 on a 4-core VM — you will degrade overall throughput.

Key Takeaways

Weighted shortest path in NebulaGraph is a two-layer problem. The graph engine owns topology — it finds all structurally valid paths within your hop budget. C# owns optimization — it applies your business objective (price, duration, distance) to select the best path. This separation is explicit and by design in NebulaGraph's architecture, and it maps cleanly to the way .NET services are already structured.

The next part of the series will look at graph projections and subgraph extraction — pulling a filtered view of the graph into memory for in-process analytics.