7
\$\begingroup\$

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;
using System.Threading.Tasks;

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];

        int[,] a; //adjacency matrix
        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();

        //adjaceny matrics
        Console.WriteLine("Adjancency matrix");
        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();
        Console.ReadLine();

        // 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();
        Console.ReadLine();

        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.ReadLine();
        }

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

        Console.WriteLine("Adjancey array");
        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();
        Console.ReadLine();
    }
 }
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Mast
    Jul 29 '20 at 11:13
  • 1
    \$\begingroup\$ (There are spelling errors in the prompts.) \$\endgroup\$
    – greybeard
    Jul 30 '20 at 21:50
  • 2
    \$\begingroup\$ Hm. What square, what spans? \$\endgroup\$
    – greybeard
    Jul 30 '20 at 21:52
6
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.