shortestpath.cpp

最短路径问题C++描述

#include <windows.h>
#include <stdio.h>

HWND hwnd;
char str[255];
const int SCREEN_WIDTH = 640, SCREEN_HEIGHT = 480;
const int UP_MARGIN = SCREEN_HEIGHT / 4, DOWN_MARGIN = SCREEN_HEIGHT / 3;
int maxX, maxY;	/* screen dimensions */
HDC hdc, memdc; /* store the virtual device handle */
HBITMAP hbit; /* store the virtual bitmap */
HBRUSH hbrush; /* store the brush handle */
HGDIOBJ hOldbit,hOldbrush;
HPEN hOldpen;	/* handle of old pen */
HPEN hRedpen, hGreenpen, hBluepen, hYellowpen;	/* create pens */
PAINTSTRUCT paintstruct;

char szWinName[] = "MyWin";	/* name of window class */
LRESULT CALLBACK WindowFunc(HWND, UINT, WPARAM, LPARAM);

#include <iostream.h>
/*
const int n = 5, mi = 65535;
int v = 1, t = 5;
int dist[n + 1], prev[n + 1];
int c[n + 1][n + 1] = {
	{mi, mi, mi, mi, mi, mi},
	{mi, 0, 10, mi, 30, 100},
	{mi, mi, 0, 50, mi, mi},
	{mi, mi, mi, 0, mi, 10},
	{mi, mi, mi, 20, 0, 60},
	{mi, mi, mi, mi, mi, 0},
};
int posX[n + 1] = {0, 200, 100, 150, 250, 300};
int posY[n + 1] = {0, 100, 180, 300, 300, 180};
*/

const int n = 15, mi = 65535;
int v = 1, t = 15;
int dist[n + 1], prev[n + 1];
int c[n + 1][n + 1];
int posX[n + 1];
int posY[n + 1];

void init();
void DisplayWeight();
void DisplayMatch();
void Dijkstra();

int WINAPI WinMain(HINSTANCE hThisInst, HINSTANCE hPrevInst, LPSTR lpszArgs,int nWinMode)
{
	MSG msg;
	WNDCLASSEX wcl;

	/* Define a window class. */
	wcl.cbSize = sizeof(WNDCLASSEX);
	wcl.hInstance = hThisInst; /* handle to this instance */
	wcl.lpszClassName = szWinName; /* window class name */
	wcl.lpfnWndProc = WindowFunc; /* window function */
	wcl.style = 0; /* default style */

	wcl.hIcon = LoadIcon(NULL,IDI_APPLICATION); /* standard icon */
	wcl.hIconSm = LoadIcon(NULL,IDI_WINLOGO); /* SMALL ICON */
	wcl.hCursor = LoadCursor(NULL,IDC_ARROW); /* cursor style */

	/* Specify name of menu resource. This will be overridden. */
	wcl.lpszMenuName = NULL; /* main menu */
	wcl.cbClsExtra = 0; /* no extra information needed */
	wcl.cbWndExtra = 0;	/* no extra information needed */
	
	/* Make the windows backgraoud white */
	wcl.hbrBackground = (HBRUSH)GetStockObject(WHITE_BRUSH);

	/* Register the window class. */
	if(!RegisterClassEx(&wcl))
		return 0;

	/* Now that a window class has been registered, a window can be created. */
	hwnd = CreateWindow(
			szWinName,	/* name of window class */
			"Dijkstra Algorithm Demo", /* title */
			WS_OVERLAPPEDWINDOW, /* window style - normal */
			CW_USEDEFAULT,	/* X coordinate - let Winodws decide */
			CW_USEDEFAULT,	/* Y coordinate - let Windows decide */
			SCREEN_WIDTH,	/* width - let Windows decide */
			SCREEN_HEIGHT,	/* height - let Windows decide */
			HWND_DESKTOP, /* no parent window */
			NULL,  /*  no menu */
			hThisInst, /* handle of this instance of the program */
			NULL /* no additional arguments */
			);

	/* Display the windows. */
	ShowWindow(hwnd, nWinMode);
	UpdateWindow(hwnd);

	init();
	Dijkstra();
	DisplayWeight();
	DisplayMatch();

	/* Create the message loop. */
	while (GetMessage(&msg, NULL, 0, 0)){
		TranslateMessage(&msg); /* translate keyboard messages */
		DispatchMessage(&msg); /* return control to Windows 98 */
	}
	return msg.wParam;
}


LRESULT CALLBACK WindowFunc(HWND hwnd, UINT message,WPARAM wParam, LPARAM lParam)
{	
	switch(message) {
	case WM_CREATE:
		/* get screen coordinates */
		maxX = GetSystemMetrics(SM_CXSCREEN);
		maxY = GetSystemMetrics(SM_CYSCREEN);

		/* make a compatible memory image */
		hdc = GetDC(hwnd);
		memdc = CreateCompatibleDC(hdc);
		
		hbit = CreateCompatibleBitmap(hdc,maxX,maxY);
		hOldbit = SelectObject(memdc,hbit);

		hbrush = (HBRUSH)GetStockObject(WHITE_BRUSH);
		hOldbrush = SelectObject(memdc,hbrush);

		PatBlt(memdc,0,0,maxX,maxY,PATCOPY);

		hRedpen = CreatePen(PS_SOLID, 2, RGB(255,0,0));
		hGreenpen = CreatePen(PS_SOLID, 2, RGB(0,255,0));
		hBluepen = CreatePen(PS_SOLID, 2, RGB(0,0,255));
		hYellowpen = CreatePen(PS_SOLID, 4, RGB(255,255,0));

		hOldpen = (HPEN)SelectObject(memdc,hRedpen);
		SelectObject(memdc,hOldpen);

		ReleaseDC(hwnd,hdc);
		break;
	case WM_PAINT:
		hdc = BeginPaint(hwnd,&paintstruct); /* get DC */
		/* now,copy memory image onto screen */
		BitBlt(hdc,0,0,maxX,maxY,memdc,0,0,SRCCOPY);
		EndPaint(hwnd,&paintstruct); /* release DC */
		break;
	case WM_DESTROY: /* terminate the program */
		/* delete pens */
		DeleteObject(hRedpen);
		DeleteObject(hGreenpen);
		DeleteObject(hBluepen);
		DeleteObject(hYellowpen);

		SelectObject(memdc,hOldbrush);
		DeleteObject(hbrush);

		SelectObject(memdc,hOldbit);
		DeleteObject(hbit);

		DeleteDC(memdc);
		PostQuitMessage(0);
		break;
	default:
		/* Let Windows 98 process any messages not specified in the preceding switch statement. */
		return DefWindowProc(hwnd,message,wParam,lParam);
	}
	return 0;
}


void Dijkstra(){
	bool s[mi];
	int i, j;
	for (i = 1; i <= n; i++){
		dist[i] = c[v][i];
		s[i] = false;
		if (dist[i] == mi) prev[i] = 0;
		else prev[i] = v;
	}
	dist[v] = 0; s[v] = true;
	for (i = 1; i < n; i++){
		int temp = mi;
		int u = v;
		for (j = 1; j <= n; j++)
			if ((!s[j]) && (dist[j] < temp)){
				u = j;
				temp = dist[j];
			}
		s[u] = true;
		for (j = 1; j <= n; j++)
			if ((!s[j]) && (c[u][j] < mi)){
				int newdist = dist[u] + c[u][j];
				if (newdist < dist[j]){
					dist[j] = newdist;
					prev[j] = u;
				}
			}
	}
}

void DisplayWeight(){
	int i, j;
	for (i = 1; i <= n; i++){
		SetPixel(memdc, posX[i], posY[i], RGB(255, 0, 0));
		sprintf(str, "%d", i);
		TextOut(memdc, posX[i], posY[i], str, strlen(str));
		for (j = 1; j <= n; j++){
			if (c[i][j] < mi){
				sprintf(str, "%d", c[i][j]);
				TextOut(memdc, (posX[i] + posX[j]) / 2, (posY[i] + posY[j]) / 2, str, strlen(str));
			}
		}
		InvalidateRect(hwnd, NULL, 1);
	}
	SelectObject(memdc, hYellowpen);
	for (i = 1; i <= n; i++){
		for (j = 1; j <= n; j++){
			if (c[i][j] > 0 && c[i][j] < mi){
				MoveToEx(memdc, posX[i], posY[i], NULL);
				LineTo(memdc, posX[j], posY[j]);
			}
		}
	}
	InvalidateRect(hwnd, NULL, 1);
}

void DisplayMatch(){
	SelectObject(memdc, hRedpen);
	int midPos = prev[t];
	MoveToEx(memdc, posX[t], posY[t], NULL);
	LineTo(memdc, posX[midPos], posY[midPos]);
	while (midPos != v){
		MoveToEx(memdc, posX[midPos], posY[midPos], NULL);
		midPos = prev[midPos];
		LineTo(memdc, posX[midPos], posY[midPos]);
	}
	sprintf(str, "从 %d 到 %d 的最短路径长度为：%d", v, t, dist[t]);
	TextOut(memdc, 100, 50, str, strlen(str));
	InvalidateRect(hwnd, NULL, 1);
}

void init(){
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			c[i][j] = mi;
	
	c[1][2] = 2; c[2][1] = 2;
	c[2][3] = 4; c[3][2] = 4;
	c[3][4] = 3; c[4][3] = 3;
	c[4][5] = 2; c[5][4] = 2;
	
	c[6][7] = 4; c[7][6] = 4;
	c[7][8] = 9; c[8][7] = 9;
	c[8][9] = 3; c[9][8] = 3;
	c[9][10] = 6; c[10][9] = 6;
	
	c[11][12] = 1; c[12][11] = 1;
	c[12][13] = 2; c[13][12] = 2;
	c[13][14] = 4; c[14][13] = 4;
	c[14][15] = 3; c[15][14] = 3;

	c[1][6] = 5; c[6][1] = 5;
	c[6][11] = 5; c[11][6] = 5;
	
	c[2][7] = 8; c[7][2] = 8;
	c[7][12] = 2; c[12][7] = 2;
	
	c[3][8] = 7; c[8][3] = 7;
	c[8][13] = 3; c[13][8] = 3;
	
	c[4][9] = 1; c[9][4] = 1;
	c[9][14] = 2; c[14][9] = 2;
	
	c[5][10] = 12; c[10][5] = 12;
	c[10][15] = 8; c[15][10] = 8;

	for (i = 1; i <= n; i++){
		posX[i] = ((i - 1) % 5 + 1) * 100;
		posY[i] = ((i - 1) / 5 + 1) * 100;
	}
}