# Implementing Dijkstra using (Fibonacci) Heap

Dijkstra Alogrithm:

```Input:  Graph G, vertices S (start), T (terminate)
Declare:  H (initially empty heap)
1: For all vertices v
2:    if v == S then v.cost := 0
3:    else v.cost := infinity
3:    Insert v into H
4: Repeat
5:    M := ExtractMin(H)
6:    For each vertex A attached to M
7:       w := cost of edge from M to A
8:       if (M.cost + w < A.cost)
9:          DecreaseKey(A,M.cost + w)
11: Until M = T
12: Output T.cost
13: Output vertices on chain of backlinks from T to S
```

Dijkstra’s algorithm sets the cost of each vertex (except the starting vertex) to infinity and puts all the vertices onto a heap. You then extract the cheapest vertex from the heap — call it M — and examine each vertex A adjacent to M. If the cost of M plus the cost of the edge joining M to A is cheaper than the current cost of A (that is, if there’s a cheap path to A through M), you create a link from A to M and decrease A’s key to represent the new cost. You continue extracting successive nodes until you reach T, the target vertex. The value of T is the cost of the shortest path. The links from T back to the starting vertex indicate the shortest path.

As you can see in Figure 1, the DecreaseKey() on line 9 is the most time-consuming operation of the inner loop. Since Dijkstra’s algorithm is important in network routing and other applications, it would be nice to find a heap implementation that makes this operation as fast as possible. This is the primary motivation for the Fibonacci heap.

—- By John Boyer

Running Time: (http://en.wikipedia.org/wiki/Dijkstra’s_algorithm)

The simplest implementation of the Dijkstra’s algorithm stores vertices of set Q in an ordinary linked list or array, and operation Extract-Min(Q) is simply a linear search through all vertices in Q. In this case, the running time is O(V^2).

For sparse graphs, that is, graphs with much less than V^2 edges, Dijkstra’s algorithm can be implemented more efficiently by storing the graph in form of adjaceny lists and using a binary heap or Fibonacci heap as a priority queue to implement the Extract-Min function. With a binary heap, the algorithm requires O((E+V)logV) time, and the Fibonacci heap improves this to O(E+VlogV).

# Sparse matrix solver

It is said that popup menu is one of the great creatures by Microsoft. And it is easy to add the popup menu in your MFC application. In fact, there are only 2 steps you need to do:
BEGIN
POPUP ""
BEGIN
MENUITEM "Drag and Drop Pasting",       ID_DSTVIEW_DDPASTING
END
END
2. Overwrite the message handler for WM_CONTEXMENU, then it is done.

{
}

# Double buffer drawing

// declare memory dc
CDC MemDC;
CBitmap MemBitmap;
// create bitmap object so that there is some space for the memory dc to draw
MemDC.CreateCompatibleDC(pDC/*NULL*/);
MemBitmap.CreateCompatibleBitmap(pDC,nWidth,nHeight);
CBitmap *pOldBit=MemDC.SelectObject(&MemBitmap);
// erase the background of the bitmap object,
// if so, you don’t need to re-define the OnEraseBkg(), I think
MemDC.FillSolidRect(0,0,nWidth,nHeight,RGB(255,255,255));

// drawing

// copy data from memory to screen
pDC->BitBlt(0,0,nWidth,nHeight,&MemDC,0,0,SRCCOPY);

// delete memory dc
MemBitmap.DeleteObject();
MemDC.DeleteDC();

# Using 2 views for a single document

In order to use more than 1 views for a singel document, one should add another document template. If adding this snippet code to InitInstance() directly, one would encounter a dialog to select different documents although you only have one type of document. Commonly, there are 2 methods to avoid this dialog: first is to declaim different resource ID for the second document template, and blabla…; second is to add the second doucment template to other place other than the InitInstance(). See:
BOOL CPhotograph2App::OnDstTemplate()
{
pDstTemplate = new CMultiDocTemplate(IDR_Photograph2TYPE,
RUNTIME_CLASS(CPhotograph2Doc),
RUNTIME_CLASS(CChildFrame), // custom MDI child frame
RUNTIME_CLASS(CDstView));

if (!pDstTemplate)
return FALSE;

ASSERT_VALID(pDstTemplate);
return TRUE;
}

Then you can create the view when necessary. Remember to InitialUpdateFrame after CreateNewFrame.
// CMainFrame message handlers
BOOL CMainFrame::OnDstWindow()
{
CMDIChildWnd* pActiveChild = MDIGetActive();
CDocument* pDocument;

if (pActiveChild == NULL ||
(pDocument = pActiveChild->GetActiveDocument()) == NULL) {
TRACE0("Warning: No active document for WindowNew command.\n");
AfxMessageBox(AFX_IDP_COMMAND_FAILURE);
return FALSE;     // command failed
}

CPhotograph2App*  pApp = (CPhotograph2App*)AfxGetApp();
ASSERT_POINTER(pApp, CPhotograph2App);
//CDocTemplate* pTemplate = pDocument->GetDocTemplate();
CMultiDocTemplate* pDstTemplate = pApp->GetDstTemplate();

ASSERT_VALID(pDstTemplate);
CFrameWnd* pFrame = pDstTemplate->CreateNewFrame(pDocument, pActiveChild);

if (pFrame == NULL)   {
TRACE0("Warning: failed to create new frame.\n");
return FALSE;     // command failed
}

pDstTemplate->InitialUpdateFrame(pFrame, pDocument);
}

# Usage of CScrollView

Generally speaking, we only need to rewrite 2 functions:
1. OnInitialUpdate()
void CSrcView::OnInitialUpdate()
{
CScrollView::OnInitialUpdate();

CPhotograph2Doc* pDoc = GetDocument();
CSize sizeTotal;
// TODO: calculate the total size of this view
sizeTotal.cx = pDoc->pSrcImg->Width();
sizeTotal.cy = pDoc->pSrcImg->Height();
SetScrollSizes(MM_TEXT, sizeTotal);
}

2. OnDraw()
// some drawing

SetScrollSizes(MM_TEXT, CSize(pDoc->pSrcImg->Width(), pDoc->pSrcImg->Height()));

CChildFrame *pParentFrame = (CChildFrame *)this->GetParentFrame();
pParentFrame->RecalcLayout();
//    ResizeParentToFit();

Probably, you may want to override the function OnEraseBkgnd();
BOOL CSrcView::OnEraseBkgnd(CDC* pDC)
{
//   Set   brush   to   desired   background   color
CBrush   backBrush(RGB(255,   255,   255));
//   Save   old   brush
CBrush*   pOldBrush   =   pDC->SelectObject(&backBrush);

CRect   rect;
pDC->GetClipBox(&rect);           //   Erase   the   area   needed
pDC->PatBlt(rect.left,   rect.top,   rect.Width(),   rect.Height(),
PATCOPY);
pDC->SelectObject(pOldBrush);

return   TRUE;
//return CScrollView::OnEraseBkgnd(pDC);
}

That’s all.

# How to live a Happy and Rewarding Life(ZZ)

Watch Butterflies or Birds.
Be grateful for good health.
Don’t interrupt.
Take a nap on Sunday afternoon.
Never deprive someone of hope.
Be thankful for every meal.
Never be afraid to say, "I’m Sorry."
Wave at children on the school bus.
Leave everything a little better than when you found it.
Leave the toilet seat in the down position.
Take time to smell the roses.
Don’t tailgate.
Keep it simple.
Enjoy good company.
Be kinder than necessary.
Wear outrageous underwear on a job interview, or to work!
Take good care of those you love.
Make it a habit to do nice things for people who never find out.
Judge your success by the degree that you enjoy peace and good health.
Be a good loser.
Be a better winner.
Be romantic.
Live so that when your children think of fairness, caring and integrity, they think of you.
Enjoy real maple syrup.
Remember other people’s birthdays.
Sing in the shower.
Resist gossip.
Don’t nag.
Don’t expect that money will bring you happiness.
Say "THANK YOU" a lot.