Wrong output of Dijkstra algorithm using C#

Question

I tried to implement dijkstra algorithm in c# but the output is wrong and it can not calculate right distance from source node.

I use an array called distance to update and store shortest path from source node. Vertex list is declared to save intermediate nodes that construct shortest path.

Here is my code :

namespace Dijkstra
{
    public class Program
    {
        static void Main(string[] args)
        {
            int[][] graph = {
                new int []{ 0, 1, 7, 0, 0 },
                new int [] { 0, 0, 4,4, 1},
                new int []{ 0, 0, 0, 3, 2 },
                new int []{ 0, 0, 0, 0, 5 },
                new int []{ 0, 0, 0, 0, 0 } };
            ShortestPath(graph, 0);
        }
        static void ShortestPath(int[][]graph,int source)
        {
            int nodes = graph.GetLength(0);
            int[] distance = new int[nodes];
            List<int> vertex = new List<int>();
            List<int> edge = new List<int>();
            int nearvertex = 0;
            int min = int.MaxValue;
            for(int i = 0; i< graph.GetLength(0); i++)
            {
                distance[i] = graph[source][i];
                if (distance[i] == 0 && i != source)
                    distance[i] = int.MaxValue;
            }
            while(nodes-1 > 0) 
            {
                min = int.MaxValue;
                for (int j = 0; j < graph.GetLength(0); j++) 
                {
                    if (distance[j] <= min && 0 < distance[j] && !vertex.Contains(j))
                    {
                        min = distance[j];
                        nearvertex = j;
                    }
                }
                edge.Add(min);
                for (int i = 0; i < graph.GetLength(0); i++) 
                {
                    if (distance[nearvertex] + graph[nearvertex][i] < distance[i] &&!vertex.Contains(i))
                    {
                        distance[i] = distance[nearvertex] + graph[nearvertex][i];
                        vertex.Add(nearvertex);
                    }
                }
                distance[nearvertex] = -1;
                nodes--;
            }
            foreach(var i in edge)
                Console.WriteLine(i);
        }
    }
}

Is there any problem with comparisons in for loops? How can i fix it?

Answer 1

There are few things wrong on your code. I'll point them for you.

See below code and comments.

static void ShortestPath(int[][] graph, int source)
{
    int nodes = graph.GetLength(0);
    int[] distance = new int[nodes];
    List<int> vertex = new List<int>(); 
    int nearvertex = 0;
    int min = int.MaxValue;
    for (int i = 0; i < distance.Length; i++)
    {
        // Distance array should be initialized to max except source vertex.
        distance[i] = int.MaxValue;
    }
    distance[source] = 0;
    while (nodes - 1 > 0)
    {
        min = int.MaxValue;
        for (int j = 0; j < graph.GetLength(0); j++)
        {
            // 0 < distance[j] --> 0 <= distance[j] : starting point distance is 0, so should be <=
            if (distance[j] <= min && 0 <= distance[j] && !vertex.Contains(j)) 
            {
                min = distance[j];
                nearvertex = j;
            }
        }

        //edge.Add(min); edge array is unnecessary.

        for (int i = 0; i < graph.GetLength(0); i++)
        {
            // you are using 0 as un-reachable distance value in your graph array, so you should check it.
            if (distance[nearvertex] + graph[nearvertex][i] < distance[i] && graph[nearvertex][i] > 0 && !vertex.Contains(i)) 
            {
                distance[i] = distance[nearvertex] + graph[nearvertex][i];
                vertex.Add(nearvertex);
            }
        }
        //distance[nearvertex] = -1;  No change required after refreshing distance array.
        nodes--;
    }
    // shortest path from source ( 0 ) will be restored in distance array.
    foreach (var i in distance) 
        Console.WriteLine(i);
}

Sample Result

// 0, 1, 7, 0, 0
// 0, 0, 4, 4, 1
// 0, 0, 0, 3, 2
// 0, 0, 0, 0, 5
// 0, 0, 0, 0, 0

0 // source vertex
1 // 0 -> 1
5 // 0 -> 1 -> 2
5 // 0 -> 1 -> 3
2 // 0 -> 1 -> 4