14,603,895 members
Rate this:
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

Rate this:

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?
v2
Patrice T 28-May-20 20:51pm

+5
phil.o 28-May-20 21:09pm

Thanks :)
BillWoodruff 28-May-20 23:01pm

+5