How to make this code of shortest Path Finder more maintainable,extendable and get better static code analysis result? I have the below code for finding the shortest path between a source node and destination node in a BiDirectional graph.It is working alright.
However, when I am running Static Code Analysis (VS2017), it is giving poor score (42) on Maintainability Index.
My questions are:


How to improve the overall code quality?
How can I make it more extendable or maintainable?
Will employing some specific Design Pattern here would have mad more sense?If yes, which one and how, can you please guide?


Here is the code below:

interface IRouter
  {
    void AddNode(string name, Dictionary&lt;string, int&gt; node);
    List&lt;string&gt; GetShortestPath(string source, string destination);
  }
public  class BaggageRouter: IRouter
  {
    Dictionary&lt;string, Dictionary&lt;string, int&gt;&gt; vertices = new Dictionary&lt;string, Dictionary&lt;string, int&gt;&gt;();

    public void AddNode(string name, Dictionary&lt;string, int&gt; node)
    {
      vertices[name] = node;
    }

    public List&lt;string&gt; GetShortestPath(string start, string finish)
    {
      #region SettingUp
      var previous = new Dictionary&lt;string, string&gt;();
      var distances = new Dictionary&lt;string, int&gt;();
      var queue = new List&lt;string&gt;();// the set of all nodes in Graph   - all nodes in the graph are unoptimized - thus are in Q

      List&lt;string&gt; path = null;

      foreach (var vertex in vertices)
      {
        if (vertex.Key == start)
        {
          distances[vertex.Key] = 0;//setting Source Node Distance=0
        }
        else
        {
          distances[vertex.Key] = int.MaxValue;//remaining all nodes are set at max distance
        }
        queue.Add(vertex.Key);
      }
      #endregion

      while (queue.Count != 0)
      {
        queue.Sort((x, y) =&gt; distances[x] - distances[y]);

        var smallest = queue[0];
        queue.Remove(smallest);//Removing the optimized Node at every Iteration

        if (smallest == finish)//Meaning we have calculated the shortest path upto destination node, so no need to calculate shortest path for remaining nodes like in original Dijkstra
        {
          path = new List&lt;string&gt;();
          while (previous.ContainsKey(smallest))
          {
            path.Add(smallest);
            smallest = previous[smallest];
          }
          path.Add(start);
          path.Reverse();
          path.Add(": " + distances[finish].ToString());//Adding the shortest path distance as last element
          break;
        }

        if (distances[smallest] == int.MaxValue)
        {
          break;//This corner-case scenario can happen if the remaining nodes are Un-reachable.
        }

        foreach (var neighbor in vertices[smallest])
        {
          var alt = distances[smallest] + neighbor.Value;
          if (distances.ContainsKey(neighbor.Key))
          {
            if (alt &lt; distances[neighbor.Key])
            {
              distances[neighbor.Key] = alt;
              previous[neighbor.Key] = smallest;
            }
          }
        }
      }

      return path;
    }
  }
How to improve the overall code quality?

I don't know much about C#, but I guess your analyzer is complaining mainly about the length of your method and its cyclomatic complexity. Try to split it in multiple well named methods and use guard conditions to reduce the nesting level of your ifs.

Maybe you could also use the ternary operator instead of the if in your first foreach to extract the common part of the if branches. But this is an highly discussed topic.

How can I make it more extendable or maintainable?

There is no real use in making something extensible, that you never plan to extend. So if you don't know possible (useful) extension points, you shouldn't desperately try to find some. You can refactor it later when you need it.

Maintainable is in general achieved by readable code and a good test base. If you are not afraid of breaking something, you can do everything with your code easily.

Will employing some specific Design Pattern here would have mad more sense?

Actually I would say, you applied the Strategy pattern here already. This is more or less the default use case, having an interface and change the path finding algorithm. (Maybe building the graph should be splitt from traversing)