How to make this code of shortest Path Finder more maintainable,extendable and get better static code analysis result?
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)