Smells like Dijkstra's Algorithm

If a solution to a problem smells like Dijkstra's Algorithm, chances are it is one. Take a look at the problem described here: http://codercareer.blogspot.com/2014/10/no-56-maximal-value-of-gifts.html. In essence, you're given a matrix (I call it a maze) and with a very strict rule to moving around, you have to find the max path from the top leftmost cell to the bottom rightmost one. The solution given in the link is a very elegant DM (Dynamic Programming) one. There is also a brute-force one which we won't get into. But I actually wanted to use this problem to exemplify the application of Dijkstra's Algorithm. It is a little overkill to use Dijkstra here, but I find this problem the perfect simple one to exemplify Dijkstra's. Dijkstra's Algorithm is a weighted BFS (breadth-first search). One needs to make use of a Priority Queue (PQ) class (down below). The overall idea of Dijkstra's is the following:

1. Determine whether your PQ will work in ascending or descending order during the dequeue operation
2. Use an auxiliary class to track the path
3. Enqueue the very first element
4. While the PQ isn't empty
1. Dequeue
2. If visited, ignore
3. Mark as visited
4. Check whether you reach the end goal ("Process")
5. Walk (if not marked)

What's interesting is that you only mark during the dequeue, not during the enqueue. What this means is that the same element can be enqueued multiple times, but that's OK, once it is dequeued and "processed", then we're sure that it won't be used again.
Code is below (the program and the PQ). Leads to the same answer: 53.

Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace MaxValueGifts
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] maze = {
                              {1, 10, 3, 8},
                              {12, 2, 9, 6},
                              {5, 7, 4, 11},
                              {3, 7, 16, 5}
                          };

            Hashtable htVisited = new Hashtable();
            PriorityQueue priorityQueue = new PriorityQueue(1000, true);
            CellConnection cell = new CellConnection(-1, -1, 0, 0, maze[0,0]);
            priorityQueue.Enqueue(cell, cell.allGifts);
            bool found = false;
            while (priorityQueue.Count > 0)
            {
                //Dequeue
                cell = (CellConnection)priorityQueue.Dequeue();
                //If visited, ignore
                int currentKey = GetKeyFromIndex(cell.rowIndexTo, cell.colIndexTo, maze.GetLength(1));
                if(htVisited.ContainsKey(currentKey))
                {
                    continue;
                }
                //Mark
                htVisited.Add(currentKey, true);
                //Check
                if (cell.rowIndexTo == maze.GetLength(0) - 1 &&
                    cell.colIndexTo == maze.GetLength(1) - 1)
                {
                    found = true;
                    break;
                }
                //Walk
                int tempKey = 0;
                if (cell.rowIndexTo + 1 < maze.GetLength(0))
                {
                    tempKey = GetKeyFromIndex(cell.rowIndexTo + 1, cell.colIndexTo, maze.GetLength(1));
                    CellConnection toCell = new CellConnection(cell.rowIndexTo, cell.colIndexTo, cell.rowIndexTo + 1, cell.colIndexTo, cell.allGifts + maze[cell.rowIndexTo + 1, cell.colIndexTo]);
                    if (!htVisited.ContainsKey(tempKey))
                    {
                        priorityQueue.Enqueue(toCell, toCell.allGifts);
                    }
                }
                if (cell.colIndexTo + 1 < maze.GetLength(1))
                {
                    tempKey = GetKeyFromIndex(cell.rowIndexTo, cell.colIndexTo + 1, maze.GetLength(1));
                    CellConnection toCell = new CellConnection(cell.rowIndexTo, cell.colIndexTo, cell.rowIndexTo, cell.colIndexTo + 1, cell.allGifts + maze[cell.rowIndexTo, cell.colIndexTo + 1]);
                    if (!htVisited.ContainsKey(tempKey))
                    {
                        priorityQueue.Enqueue(toCell, toCell.allGifts);
                    }
                }
            }
            if (found)
            {
                Console.WriteLine("Max gift: {0}", cell.allGifts);
            }
        }
        static int GetKeyFromIndex(int row, int col, int MAXCOL)
        {
            return row * MAXCOL + col;
        }
        static void GetIndexFromKey(int key, int MAXCOL, out int row, out int col)
        {
            row = key / MAXCOL;
            col = key % MAXCOL;
        }
    }
    class CellConnection
    {
        public int rowIndexFrom = 0;
        public int colIndexFrom = 0;
        public int rowIndexTo = 0;
        public int colIndexTo = 0;
        public int allGifts = 0;
        private CellConnection() { }
        public CellConnection(int rowIndexFrom, int colIndexFrom, int rowIndexTo, int colIndexTo, int allGifts)
        {
            this.rowIndexFrom = rowIndexFrom;
            this.colIndexFrom = colIndexFrom;
            this.rowIndexTo = rowIndexTo;
            this.colIndexTo = colIndexTo;
            this.allGifts = allGifts;
        }
    }
}

PriorityQueue.cs
using System;
using System.Linq;
using System.Text;
using System.Collections;
using System.Collections.Generic;
namespace MaxValueGifts
{
    public class PriorityQueue
    {
        public struct HeapEntry
        {
            private object item;
            private long priority;
            public HeapEntry(object item, long priority)
            {
                this.item = item;
                this.priority = priority;
            }
            public object Item
            {
                get
                {
                    return item;
                }
            }
            public long Priority
            {
                get
                {
                    return priority;
                }
            }
        }
        private long count;
        private long capacity;
        private bool descending; //Means that the max element at the top
        private HeapEntry[] heap;
        public long Count
        {
            get
            {
                return this.count;
            }
        }
        public PriorityQueue(long capacity, bool descending)
        {
            this.capacity = capacity;
            this.descending = descending;
            heap = new HeapEntry[this.capacity];
        }
        public object Dequeue()
        {
            object result = heap[0].Item;
            count--;
            trickleDown(0, heap[count]);
            return result;
        }
        public void Enqueue(object item, long priority)
        {
            count++;
            bubbleUp(count - 1, new HeapEntry(item, priority));
        }
        private void bubbleUp(long index, HeapEntry he)
        {
            long parent = (index - 1) / 2;
            // note: (index > 0) means there is a parent
            while (
                   (index > 0) &&
                   ((this.descending && heap[parent].Priority < he.Priority) || (!this.descending && heap[parent].Priority > he.Priority))
                  )
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
        private void trickleDown(long index, HeapEntry he)
        {
            long child = (index * 2) + 1;
            while (child < count)
            {
                if (
                    ((child + 1) < count) &&
                    ((this.descending && heap[child].Priority < heap[child + 1].Priority) || (!this.descending && heap[child].Priority > heap[child + 1].Priority))
                   )
                {
                    child++;
                }
                heap[index] = heap[child];
                index = child;
                child = (index * 2) + 1;
            }
            bubbleUp(index, he);
        }
    }
}