Breadth First Search: Shortest Reach

  • + 0 comments

    C# solution

    public static List bfs(int n, int m, List> edges, int s) { //Initializing graph var edgeWeight = 6; var graph = new Dictionary>(); for (int i = 1; i <= n; i++) graph[i] = new List();

    //Filling graph
    foreach(var edge in edges)
    {
        var node1 = edge[0];
        var node2 = edge[1];
        graph[node1].Add(node2);
        graph[node2].Add(node1);
    }
    
    //Initializing distances
    var queue = new Queue<int>();
    var distance = new int[n + 1];
    for (int i = 1; i <= n; i++)
        distance[i] = -1;
    distance[s] = 0;
    queue.Enqueue(s);
    
    //BFS
    while(queue.Any())
    {
        var node = queue.Dequeue();
        foreach(var neighbor in graph[node])
        {
            if (distance[neighbor] == -1)
            {
                distance[neighbor] = distance[node] + edgeWeight;
                queue.Enqueue(neighbor);
            }                    
        }
    }
    
    //Filling result distances
    var result = new List<int>();
    for (int i = 1; i <= n; i++)
    {
        if (i == s)
            continue;
    
        result.Add(distance[i]);
    }
    
    return result;
    

    }