Member Avatar for adem87

i have a project that it find the shortest bakery in c# . i written a program that save vertex and edge and drowing when opening the program. bu i need a code that find the nearest bakery. please write the needing code below this.
i have this

vertex.id vertex.x, vertex.y
and edge its loaded this
                Edge edge = edges.ElementAt(i);// get verr


            please help me
  • 2 Contributors
  • 1 Reply
  • 258 Views
  • 2 Hours Discussion Span
  • Latest Post Latest Post by ddanbe

Dani AI

Generated

As hinted, the right approach for “nearest bakery along the graph” is a shortest‑path search (Dijkstra) that stops as soon as it removes a bakery node from the priority queue. That returns the closest bakery by path cost (not straight‑line distance). Use BFS instead if edges are unweighted.

Expectations: each vertex should have an Id, coordinates (if you need Euclidean weights), a flag like IsBakery, and a list of outgoing edges (target Id + weight). If your edges don’t carry weights, compute weight = Euclidean distance between the two vertex coordinates.

Example (C#; .NET 6+ PriorityQueue). It runs Dijkstra from a single source and returns the nearest bakery node id (or -1):

class Vertex { public int Id; public double X, Y; public bool IsBakery; public List<Edge> Edges = new(); }
class Edge   { public int To; public double Weight; }

int FindNearestBakery(int sourceId, Dictionary<int,Vertex> graph)
{
    var dist = graph.Keys.ToDictionary(k => k, k => double.PositiveInfinity);
    var prev = new Dictionary<int,int?>();
    var pq = new PriorityQueue<int,double>();
    dist[sourceId] = 0;
    pq.Enqueue(sourceId, 0);

    var seen = new HashSet<int>();
    while (pq.Count > 0) {
        pq.TryDequeue(out int u, out double d);
        if (!seen.Add(u)) continue;
        if (graph[u].IsBakery && u != sourceId) return u; // nearest bakery found
        foreach (var e in graph[u].Edges) {
            double alt = d + e.Weight;
            if (alt < dist[e.To]) {
                dist[e.To] = alt;
                prev[e.To] = u;
                pq.Enqueue(e.To, alt);
            }
        }
    }
    return -1;
}

Notes and quick tips:

  • If you only want straight‑line nearest bakery, skip graph search and compare Euclidean distances to each bakery.
  • Edge weights must be non‑negative for Dijkstra. If you have negatives, use Bellman‑Ford.
  • For many queries, run a multi‑source Dijkstra by enqueueing all bakery nodes with distance 0 once; that computes nearest bakery for every vertex in a single run.
  • If you target older .NET, replace PriorityQueue with a small binary‑heap or SortedSet implementation.
  • Reconstruct paths with the prev map if you need the actual route.
Member Avatar for ddanbe

Did you read this article?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.