# Dijkstra algorithm C#

I have implementing a simple version of Dijkstra's algorithm in C#. Could this be made more efficient? Does it need to be modified?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace dijkstra
{
class Program
{
static void Main(string[] args)
{
int n = 5; //nodes
int m = 100; //size of square
int mm = 999; //maximum cost
double t = m / 0.75; //distance

float[] x, y; //x and y coordinates

x = new float[n + 1];
y = new float[n + 1];

float[,] c; //cost matrix
c = new float[n + 1, n + 1];

a = new int[n + 1, n + 1];

//distance array
float[] d;
d = new float[n + 1];

//span array
int[] sa;
sa = new int[n + 1];

Random r = new Random();

//randomise coordinates

for (int i = 1; i <= n; i++)
{
x[i] = m * (float)r.NextDouble();
y[i] = m * (float)r.NextDouble();
d[i] = mm;
sa[i] = 0;

}
//coordinates
Console.WriteLine("Coordinates");
for (int i = 1; i <= n; i++)
Console.WriteLine(i + ": (" + x[i].ToString("0.00") + " , " + y[i].ToString("0.00") + " )");
Console.WriteLine();

//span array
Console.WriteLine("Spanne array");
for (int i = 1; i <= n; i++)
Console.Write(i + ": " + sa[i] + " ");
Console.WriteLine();
Console.WriteLine();

//calculate distance costs
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{

c[i, j] = (float)Math.Sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
if (c[i, j] > t)
c[i, j] = mm;
a[i, j] = 0;
}

Console.WriteLine("Starting values: ");
Console.WriteLine();

// distances
Console.WriteLine("Cost matrix");
for (int i = 1; i <= n; i++)
{

for (int j = 1; j <= n; j++)
if ((i >= j) || (c[i, j] > t)) //if i is greater than j or is the 999 distance then
Console.Write(" -- ");
else
Console.Write(" " + c[i, j].ToString("00.00"));
Console.WriteLine();
}

Console.WriteLine();

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
if (i >= j)
Console.Write(" -");
else
Console.Write(" " + a[i, j]);
Console.WriteLine();

}
Console.WriteLine();

// starting node
int start = r.Next(1, n + 1);
Console.WriteLine("Start at node " + start + " ...");
Console.WriteLine();
sa[start] = 1;
d[start] = 0;

Console.WriteLine("Span array");
for (int i = 1; i <= n; i++)
Console.Write(i + ": " + sa[i] + "  ");
Console.WriteLine();
Console.WriteLine();

Console.WriteLine("Distance array");
for (int i = 1; i <= n; i++)
Console.Write(i + ": " + d[i].ToString("0.00") + "  ");
Console.WriteLine();
Console.WriteLine();

for (int k = 1; k < n; k++)
{
float shortestDistance = mm;
int iShortest = 0, jShortest = 0, spannedShortest = 0, unspannedShortest = 0;
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++)
if ((sa[i] == 1) && (sa[j] == 0))
{
if (d[i] + c[i, j] < shortestDistance)
{
shortestDistance = d[i] + c[i, j];
iShortest = i;
jShortest = j;
spannedShortest = i;
unspannedShortest = j;
}
}
else if ((sa[i] == 0) && (sa[j] == 1))
{
if (d[j] + c[i, j] < shortestDistance)
{
shortestDistance = d[j] + c[i, j];
iShortest = i;
jShortest = j;
spannedShortest = j;
unspannedShortest = i;
}
}
a[iShortest, jShortest] = 1;
Console.WriteLine("Joining " + iShortest + " and " + jShortest);
sa[unspannedShortest] = 1;
d[unspannedShortest] = d[spannedShortest] + c[iShortest, jShortest];
Console.WriteLine("Distance to " + unspannedShortest + " is " + d[unspannedShortest].ToString("00.00"));
}

Console.WriteLine("Spanned array");
for (int i = 1; i <= n; i++)
Console.Write(i + ": " + sa[i] + "  ");
Console.WriteLine();
Console.WriteLine();

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
if (i >= j)
Console.Write(" -");
else
Console.Write(" " + a[i, j]);
Console.WriteLine();
}
Console.WriteLine();

// look at the distance array
Console.WriteLine("Distance array");
for (int i = 1; i <= n; i++)
Console.Write(i + ": " + d[i].ToString("0.00") + "  ");
Console.WriteLine();
Console.WriteLine();
}
}
}

• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
– Mast
Commented Jul 29, 2020 at 11:13
• (There are spelling errors in the prompts.) Commented Jul 30, 2020 at 21:50
• Hm. What square, what spans? Commented Jul 30, 2020 at 21:52

Symbolic Constants
It is good that you named these numeric constants, but they are constants so rather than declare them as variables, declare them as constants.

        static void Main(string[] args)
{
const int n = 5; //nodes
const int m = 100; //size of square
const int mm = 999; //maximum cost
const double t = m / 0.75; //distance


DRY Code
There is a programming principle called the Don't Repeat Yourself Principle sometimes referred to as DRY code. If you find yourself repeating the same code multiple times it is better to encapsulate it in a function. If it is possible to loop through the code that can reduce repetition as well.

This code is almost repeating and can be encapsulated in a function.

                            {
shortestDistance = d[i] + c[i, j];
iShortest = i;
jShortest = j;
spannedShortest = i;
unspannedShortest = j;
}


Other code that could be put into a function is the code that prints out the arrays.

Use Functions to Break Up the Code
When designing and writing software the best problem solving method is to decompose the problem into smaller and smaller parts. This makes coding much easier and limits the complexity of the code. One example is the code above that is reusable. Smaller blocks of code are easier to read, write, debug and maintain.

Format the Output
There are ways to format Console.Write() and Console.WriteLine():

            Console.WriteLine("Coordinates");
for (int i = 1; i <= n; i++)
{
Console.WriteLine("{0:D}: ({1:F}, {2:F})", i, x[i].ToString("0.00"), y[i].ToString("0.00"));
}
Console.WriteLine();


Rather than using Console.WriteLine(); use Console.WriteLine("\n"); or Console.Write("\n\n"); to insert blank lines.

This is a beginning and I'm out of time. After you have made functions you might want to post a second question with a link to this one.