a star dijkstra in csharp

Here's a C# implementation of Dijkstra's algorithm using an adjacency list to represent the graph:


main.cs
using System;
using System.Collections.Generic;

class Dijkstra
{
    // Returns the shortest distances from the start node to every other node in the graph
    public static Dictionary<int, int> ShortestPaths(Dictionary<int, List<Tuple<int, int>>> graph, int start)
    {
        // Initialize the distances dictionary with all nodes set to "infinity" except for the start node
        Dictionary<int, int> distances = new Dictionary<int, int>();
        foreach (int node in graph.Keys)
        {
            distances.Add(node, int.MaxValue);
        }
        distances[start] = 0;

        // Initialize the set of unvisited nodes
        HashSet<int> unvisited = new HashSet<int>(graph.Keys);

        while (unvisited.Count > 0)
        {
            // Find the unvisited node with the smallest distance
            int closestNode = -1;
            int closestDistance = int.MaxValue;
            foreach (int node in unvisited)
            {
                if (distances[node] < closestDistance)
                {
                    closestNode = node;
                    closestDistance = distances[node];
                }
            }

            // For each neighbor of the closest node, update its distance if a shorter path was found
            foreach (Tuple<int, int> neighbor in graph[closestNode])
            {
                int altDistance = distances[closestNode] + neighbor.Item2;
                if (altDistance < distances[neighbor.Item1])
                {
                    distances[neighbor.Item1] = altDistance;
                }
            }

            // Mark the closest node as visited
            unvisited.Remove(closestNode);
        }

        return distances;
    }
}
1722 chars
51 lines

To use this implementation, you would create an adjacency list representing your graph, where the keys are the nodes and the values are lists of tuples representing that node's neighbors and edge weights. For example, the following code creates a graph with 5 nodes and the edges (0,1), (0,2), (1,2), (1,3), (2,3), and (2,4):


main.cs
Dictionary<int, List<Tuple<int, int>>> graph = new Dictionary<int, List<Tuple<int, int>>>();
graph.Add(0, new List<Tuple<int, int>>() { new Tuple<int, int>(1, 1), new Tuple<int, int>(2, 4) });
graph.Add(1, new List<Tuple<int, int>>() { new Tuple<int, int>(2, 2), new Tuple<int, int>(3, 5) });
graph.Add(2, new List<Tuple<int, int>>() { new Tuple<int, int>(3, 1), new Tuple<int, int>(4, 3) });
graph.Add(3, new List<Tuple<int, int>>());
graph.Add(4, new List<Tuple<int, int>>());
479 chars
7 lines

You could then call the ShortestPaths method with the graph and start node to get the shortest distances to every other node:


main.cs
Dictionary<int, int> distances = Dijkstra.ShortestPaths(graph, 0);
foreach (int node in distances.Keys)
{
    Console.WriteLine("{0}: {1}", node, distances[node]);
}
166 chars
6 lines

similar csharp code snippets

get the shortest path in csharp

depth first search in csharp

dijkstra path finding in csharp

insert an element into an array at a specific index in csharp

find the index of an element in an array in csharp

remove an element from the beginning of an array in csharp

remove an element from the middle of an array in csharp

remove an element from an array at a specific index in csharp

sort an array in csharp

add an element to the beginning of an array in csharp

related categories