Click here to Skip to main content
14,603,895 members
Rate this:
Please Sign up or sign in to vote.
See more:
// A 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"); 
    } 
  
    // Funtion 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 Code 
    public static void Main() 
    { 
        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(); 
        t.dijkstra(graph, 0); 
    } 
} 


What I have tried:

Please, someone understand this many zeros in "graph"?
I´m seeing many videos of this algorithm, but i can figure out what are those zeros.
Can somebody help me?
Posted
Updated 28-May-20 14:04pm

1 solution

Rate this:
Please Sign up or sign in to vote.

Solution 1

In an adjacency matrix of a graph, a value of zero means that there is no edge between corresponding vertices.
For example, in the matrix you have shown, note that the values in the diagonal are all zeroes, because there is no loop edge on any node.
For values outside the diagonal, you can see that there is no edge between first vertex and third, fourth, fifth, sixth, seventh and ninth. There are only edges between first vertex and second and eighth.
Vertex Nb             1  2  3  4  5  6  7  8  9
First vertex's edges  0  4  0  0  0  0  0  8  0

And the same for other lines of the matrix (second line = second vertex, etc.).
Maybe you should have a deeper look at the core graph theory?
Adjacency matrix - Wikipedia[^]
   
v2
Comments
Patrice T 28-May-20 20:51pm
   
+5
phil.o 28-May-20 21:09pm
   
Thanks :)
BillWoodruff 28-May-20 23:01pm
   
+5

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100