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)
10:         A.backlink := M
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).

IDR_MENU1 MENU
BEGIN
 POPUP ""
    BEGIN
  MENUITEM "Poisson Image Editing",       ID_DSTVIEW_POISSON
  MENUITEM "Drag and Drop Pasting",       ID_DSTVIEW_DDPASTING
 END
END

void CDstView::OnContextMenu(CWnd* /*pWnd*/, CPoint point)
{
      CMenu   popupmenu;  
      popupmenu.LoadMenu(IDR_MENU1);  
      CMenu*   popup=popupmenu.GetSubMenu(0);  
      popup->TrackPopupMenu(TPM_LEFTALIGN,point.x,point.y,this);  

}

// 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();

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;

 AddDocTemplate(pDstTemplate);          
  
 ASSERT_VALID(pDstTemplate); 
 return TRUE;
}

 

// 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);

}