CareerCup

if weights are non-negative and there are no cycles allowed: Djikstra's Algorithm
if weights can be negative and possible negative cycles may exist: Bellman-Ford Algorithm

Yes..We can use DP to get the shortest path here..Complexity would be O(n2)

Code:

public int getMinCostPath(int a[][]) {
		int tc[][] = new int[a.length][a.length];
		tc[0][0] = a[0][0];
		for (int i = 1; i < a.length; i++) {
			tc[i][0] = tc[i - 1][0] + a[i][0];
		}

		for (int j = 1; j < a.length; j++) {
			tc[0][j] = tc[0][j - 1] + a[0][j];
		}

		for (int i = 1; i < a.length; i++) {
			for (int j = 1; j < a.length; j++) {
				tc[i][j] = min(tc[i - 1][j], tc[i][j - 1], tc[i - 1][j - 1])
						+ a[i][j];
			}

		}

		return tc[a.length - 1][a.length - 1];
	}

Here the start and end are first and last node.That can be modified.

if the path is only allowd to move right or down or rightdown then the algorithm like DP can be used. else Djikstra should be used.
Suppose
1 0 1
1 0 1
0 0 1
0 1 0 start point is (0, 0) end point is (3, 2) under this condition, Djikstra should be used.

Djikstra's Algorithm Implementation in C#

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Test.CareerCup
{
    public class C17297667
    {
        private int size;
        public int[] weight;
        private int[] previous;
        private int[] distance;
        private List<int> set = new List<int>();

        public C17297667(int size)
        {
            this.size = size;
        }

        public void Init()
        {
            weight = new int[size * size];
            previous = new int[size * size];
            distance = new int[size * size];

            var random = new Random();
            // init weight
            for (int i = 0; i < size * size; i++)
            {
                weight[i] = random.Next(1, 20);
                previous[i] = -1;
                distance[i] = int.MaxValue;
                set.Add(i);
            }
        }

        public void ShowMatrix()
        {
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    Console.Write("{0,4}, ", weight[i * size + j]);
                }
                Console.WriteLine();
            }
        }

        private void CheckDistance(int current, int target)
        {
            int tmp_dist = distance[current] + weight[target];
            if (tmp_dist < distance[target])
            {
                distance[target] = tmp_dist;
                previous[target] = current;
            }
        }

        public IEnumerable<int> GetShortestPath(int start, int end, out int minValue)
        {
            List<int> path = new List<int>();
            distance[start] = 0;

            while (set.Count > 0)
            {
                // find point with min distance in set
                int node = (from p in set orderby distance[p] select p).First();

                // remove it from set
                set.Remove(node);

                // if node == end, reach the target
                if (node == end) break;

                // check neighbors
                // up
                if (node - size > 0)
                {
                    CheckDistance(node, node - size);
                }
                // down
                if (node + size < size * size)
                {
                    CheckDistance(node, node + size);
                }
                // left
                if (node % size != 0)
                {
                    CheckDistance(node, node - 1);
                }
                // right
                if (node % size != size - 1)
                {
                    CheckDistance(node, node + 1);
                }
            }

            minValue = distance[end];
            if (distance[end] == int.MaxValue)
            {
                return null; // no result
            }
            else
            {
                int current = end;
                do
                {
                    path.Insert(0, current);
                    current = previous[current];
                } while (current != start);
                path.Insert(0, current);

                return path;
            }
        }
    }
}

Calling:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Test.CareerCup;

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            FindShortestPath();
        }

        static void FindShortestPath()
        {
            C17297667 c = new C17297667(8);
            c.Init();
            c.ShowMatrix();

            int minValue;
            var path = c.GetShortestPath(0, 63, out minValue);

            Console.WriteLine("Min path value = " + minValue);
            Console.WriteLine("Min path is:");
            foreach (var p in path)
            {
                Console.WriteLine("{0}, {1}, wight = {2}", p / 8, p % 8, c.weight[p]);
            }
        }
    }
}

Implementing Djikstra's Algorithm here is not easy. I guess a lot of modifications are to be done for it. DP solution is what is best.