How to find Shortest Paths from Source to all Vertices using Dijkstra’s Algorithm

// C# program for Dijkstra's single
// source shortest path algorithm.
// The program is for adjacency matrix
// representation of the graph
using System;

class GFG {
    // A utility function to find the
    // vertex with minimum distance
    // value, from the set of vertices
    // not yet included in shortest
    // path tree
    static int V = 9;
    int minDistance(int[] dist, bool[] sptSet)
    {
        // Initialize min value
        int min = int.MaxValue, min_index = -1;

        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }

        return min_index;
    }

    // A utility function to print
    // the constructed distance array
    void printSolution(int[] dist)
    {
        Console.Write("Vertex \t\t Distance "
                      + "from Source\n");
        for (int i = 0; i < V; i++)
            Console.Write(i + " \t\t " + dist[i] + "\n");
    }

    // Function that implements Dijkstra's
    // single source shortest path algorithm
    // for a graph represented using adjacency
    // matrix representation
    void dijkstra(int[, ] graph, int src)
    {
        int[] dist
            = new int[V]; // The output array. dist[i]
        // will hold the shortest
        // distance from src to i

        // sptSet[i] will true if vertex
        // i is included in shortest path
        // tree or shortest distance from
        // src to i is finalized
        bool[] sptSet = new bool[V];

        // Initialize all distances as
        // INFINITE and stpSet[] as false
        for (int i = 0; i < V; i++) {
            dist[i] = int.MaxValue;
            sptSet[i] = false;
        }

        // Distance of source vertex
        // from itself is always 0
        dist[src] = 0;

        // Find shortest path for all vertices
        for (int count = 0; count < V - 1; count++) {
            // Pick the minimum distance vertex
            // from the set of vertices not yet
            // processed. u is always equal to
            // src in first iteration.
            int u = minDistance(dist, sptSet);

            // Mark the picked vertex as processed
            sptSet[u] = true;

            // Update dist value of the adjacent
            // vertices of the picked vertex.
            for (int v = 0; v < V; v++)

                // Update dist[v] only if is not in
                // sptSet, there is an edge from u
                // to v, and total weight of path
                // from src to v through u is smaller
                // than current value of dist[v]
                if (!sptSet[v] && graph[u, v] != 0
                    && dist[u] != int.MaxValue
                    && dist[u] + graph[u, v] < dist[v])
                    dist[v] = dist[u] + graph[u, v];
        }

        // print the constructed distance array
        printSolution(dist);
    }

    // Driver's Code
    public static void Main()
    {
        /* Let us create the example
graph discussed above */
        int[, ] graph
            = new int[, ] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                            { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                            { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                            { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                            { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                            { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                            { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                            { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                            { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
        GFG t = new GFG();

        // Function call
        t.dijkstra(graph, 0);
    }
}

// This code is contributed by ChitraNayal

using System;
using System.Collections.Generic;

// This class represents a directed graph using
// adjacency list representation
public class Graph
{
  private const int INF = 2147483647;

  private int V;
  private List<int[]>[] adj;

  public Graph(int V)
  {    
    // No. of vertices
    this.V = V;
    // In a weighted graph, we need to store vertex
    // and weight pair for every edge
    this.adj = new List<int[]>[V];

    for (int i = 0; i < V; i++)
    {
      this.adj[i] = new List<int[]>();
    }
  }

  public void AddEdge(int u, int v, int w)
  {
    this.adj[u].Add(new int[] { v, w });
    this.adj[v].Add(new int[] { u, w });
  }

  // Prints shortest paths from src to all other vertices
  public void ShortestPath(int src)
  {
    // Create a priority queue to store vertices that
    // are being preprocessed.
    SortedSet<int[]> pq = new SortedSet<int[]>(new DistanceComparer());

    // Create an array for distances and initialize all
    // distances as infinite (INF)
    int[] dist = new int[V];
    for (int i = 0; i < V; i++)
    {
      dist[i] = INF;
    }

    // Insert source itself in priority queue and initialize
    // its distance as 0.
    pq.Add(new int[] { 0, src });
    dist[src] = 0;

    /* Looping till priority queue becomes empty (or all
        distances are not finalized) */
    while (pq.Count > 0)
    {
      // The first vertex in pair is the minimum distance
      // vertex, extract it from priority queue.
      // vertex label is stored in second of pair (it
      // has to be done this way to keep the vertices
      // sorted by distance)
      int[] minDistVertex = pq.Min;
      pq.Remove(minDistVertex);
      int u = minDistVertex[1];

      // 'i' is used to get all adjacent vertices of a
      // vertex
      foreach (int[] adjVertex in this.adj[u])
      {
        // Get vertex label and weight of current
        // adjacent of u.
        int v = adjVertex[0];
        int weight = adjVertex[1];

        // If there is a shorter path to v through u.
        if (dist[v] > dist[u] + weight)
        {
          // Updating distance of v
          dist[v] = dist[u] + weight;
          pq.Add(new int[] { dist[v], v });
        }
      }
    }

    // Print shortest distances stored in dist[]
    Console.WriteLine("Vertex Distance from Source");
    for (int i = 0; i < V; ++i)
      Console.WriteLine(i + "\t" + dist[i]);
  }

  private class DistanceComparer : IComparer<int[]>
  {
    public int Compare(int[] x, int[] y)
    {
      if (x[0] == y[0])
      {
        return x[1] - y[1];
      }
      return x[0] - y[0];
    }
  }
}

public class Program
{    
  // Driver Code
  public static void Main()
  {
    // create the graph given in above figure
    int V = 9;
    Graph g = new Graph(V);

    // making above shown graph
    g.AddEdge(0, 1, 4);
    g.AddEdge(0, 7, 8);
    g.AddEdge(1, 2, 8);
    g.AddEdge(1, 7, 11);
    g.AddEdge(2, 3, 7);
    g.AddEdge(2, 8, 2);
    g.AddEdge(2, 5, 4);
    g.AddEdge(3, 4, 9);
    g.AddEdge(3, 5, 14);
    g.AddEdge(4, 5, 10);
    g.AddEdge(5, 6, 2);
    g.AddEdge(6, 7, 1);
    g.AddEdge(6, 8, 6);
    g.AddEdge(7, 8, 7);
    g.ShortestPath(0);
  }
}

// this code is contributed by bhardwajji