dijkstra

ダイクストラはかくかたりき

#include <windows.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

#define BUTTON_START    0
#define BUTTON_RESET    1
#define BUTTON_MINEDGE  2

#define WINDOW_HEIGHT 450
#define WINDOW_WIDTH  450

#define NODE_NUM 30
#define NODE_R   7

POINT   node[NODE_NUM];
int  dmat[NODE_NUM][NODE_NUM]; 
int  is_edge[NODE_NUM][NODE_NUM]; 
int  min_edge[NODE_NUM][NODE_NUM];   
int  min_dist[NODE_NUM];       
int  start = 0;               

HBRUSH  first_color; 
HBRUSH  node_color;    
HPEN    edge_color;  
HPEN    me_color;     

void dijkstra(void)
{
    int done[NODE_NUM];
    int min, min_idx;
    int i, j, k, t;

    for (i = 0;i < NODE_NUM;i++)
        min_dist[i] = INT_MAX;
    min_dist[start] = 0;
    memset(done, 0, sizeof(done));
    memset(min_edge, 0, sizeof(min_edge));
    for (i = 1;i < NODE_NUM;i++) {
        min = INT_MAX;
        for (j = 0;j < NODE_NUM;j++) {
            if (!done[j] && min_dist[j] < min) {
                min = min_dist[j];
                min_idx = j;
            }
        }
        done[min_idx] = 1;
        for (k = 0;k < NODE_NUM;k++) {
            if (!done[k] && dmat[min_idx][k] != -1) {
                if (min_dist[k] > min_dist[min_idx]+dmat[min_idx][k]) {
                    for (t = 0;t < NODE_NUM;t++)
                        min_edge[k][t] = 0;
                    min_edge[k][min_idx] = 1;
                }
                min_dist[k] = min(min_dist[k], min_dist[min_idx]+dmat[min_idx][k]);

            }
        }
    }
}

int distance(int sx, int sy, int ex, int ey)
{
    int x2 = (sx-ex)*(sx-ex);
    int y2 = (sy-ey)*(sy-ey);

    return (int)sqrt(x2+y2);
}

void init_node(void)
{
    int i;

    for (i = 0;i < NODE_NUM;i++) {
        do {
            node[i].x = rand()%(WINDOW_HEIGHT-50)+20;
            node[i].y = rand()%(WINDOW_HEIGHT-50)+20;
        } while (node[i].x >= 360 && node[i].y <=70);
    }
}

void init_edge(void)
{
    int i, k, dist, cnt, rnd;
    int n = 10;

    memset(min_edge, 0, sizeof(min_edge));
    memset(is_edge, 0, sizeof(is_edge));

    for (i = 0;i < NODE_NUM;i++) {
        cnt = 0;
        for (k = 0;k < NODE_NUM;k++) {
            dist = distance(node[i].x, node[i].y, node[k].x, node[k].y);
            if (rand()%n==0 && dist < 250) {
                is_edge[i][k] = is_edge[k][i] = 1;
                cnt++;
            }
        }
        if (cnt == 0) {
            while ((rnd=rand()%NODE_NUM) == i)
                /* rnd != i になるまで回す */;

            is_edge[i][rnd] = is_edge[rnd][i] = 1;
        }
    }

}

void init_dmat(void)
{
    int i, k;

    memset(dmat, -1, sizeof(dmat));
    for (i = 0;i < NODE_NUM;i++)
        for (k = i+1;k < NODE_NUM;k++)
            if (is_edge[i][k] == 1)
                dmat[i][k] = dmat[k][i] = distance(node[i].x, node[i].y,node[k].x, node[k].y);

    for (i = 0;i < NODE_NUM;i++)
        dmat[i][i] = 0;
}

void init_pb(void)
{
    me_color    = CreatePen(PS_SOLID, 1, RGB(0xff, 0, 0));
    edge_color  = CreatePen(PS_SOLID, 0, RGB(0, 0, 0));
    first_color = CreateSolidBrush(RGB(0xff, 0, 0));
    node_color  = CreateSolidBrush(RGB(0xff, 0xff, 0xff));
}

void delete_pb(void)
{
    DeleteObject(me_color);
    DeleteObject(edge_color);
    DeleteObject(first_color);
    DeleteObject(node_color);
}

void DrawLine(HDC hdc, int xs, int ys, int xe, int ye)
{
    MoveToEx(hdc, xs, ys, NULL);
    LineTo(hdc, xe, ye);
    MoveToEx(hdc, 0, 0, NULL);
}

void DrawCircle(HDC hdc, int x, int y)
{
    Ellipse(hdc, x-NODE_R, y-NODE_R, x+NODE_R, y+NODE_R);
}

void Draw_Node(HDC hdc)
{
    int i;

    SelectObject(hdc ,edge_color);
    SelectObject(hdc ,first_color);
    DrawCircle(hdc, node[start].x, node[start].y);

    SelectObject(hdc , node_color);
    for (i = 0;i < NODE_NUM;i++)
        if (i != start)
            DrawCircle(hdc, node[i].x, node[i].y);

}

void Draw_Edge(HDC hdc)
{
    int i, k;

    SelectObject(hdc, edge_color);
    for (i = 0;i < NODE_NUM;i++) {
        for (k = i+1;k < NODE_NUM;k++) {
            if (is_edge[i][k]) {
                DrawLine(hdc, node[i].x, node[i].y, node[k].x, node[k].y);
            }
        }
    }

}

void Draw_MinEdge(HDC hdc)
{
    int i, k;

    SelectObject(hdc, me_color);
    for (i = 0;i < NODE_NUM;i++) {
        for (k = 0;k < NODE_NUM;k++) {
            if (min_edge[i][k])
                DrawLine(hdc, node[i].x, node[i].y, node[k].x, node[k].y);  
        }
    }
}

int SearchNode(POINT pt)
{
    int x = pt.x;
    int y = pt.y;
    int i;

    for (i = 0;i < NODE_NUM;i++) {
        if (i == start)
            continue;
        if (node[i].x-NODE_R <= x && x <= node[i].x+NODE_R &&
            node[i].y-NODE_R <= y && y <= node[i].y+NODE_R) {
                start = i;
                return 1;
        }
    }

    return 0;
}

void output_data(void)
{
    FILE *fp;
    int i, k;

    fp = fopen("result.txt", "w");

    fprintf(fp, "ノード\n");
    for (i = 0;i < NODE_NUM;i++)
        fprintf(fp, "%2d: (x,y) = (%3ld, %3ld)\n", i, node[i].x, node[i].y);
    fprintf(fp, "辺があるか\n");
    for (i = 0;i < NODE_NUM;i++) {
        for (k = 0;k < NODE_NUM;k++)
            fprintf(fp, "%d ", is_edge[i][k]);
        fprintf(fp, "\n");
    }
    fprintf(fp, "距離行列\n");
    for (i = 0;i < NODE_NUM;i++) {
        for (k = 0;k < NODE_NUM;k++)
            fprintf(fp, "%3d ", dmat[i][k]);
        fprintf(fp, "\n");
    }
    fprintf(fp, "最短距離に関わる辺\n");
    for (i = 0;i < NODE_NUM;i++) {
        for (k = 0;k < NODE_NUM;k++)
            fprintf(fp,"%d ", min_edge[i][k]);
        fprintf(fp, "\n");
    }
    fprintf(fp, "最短距離\n");
    for (i = 0;i < NODE_NUM;i++)
        fprintf(fp, "%d %d\n", i,min_dist[i]);
}

LRESULT CALLBACK WndProc(HWND hwnd , UINT msg , WPARAM wp , LPARAM lp)
{
    HDC hdc;
    PAINTSTRUCT ps;
    POINT pt;
    static int visible_edge = 1;

    switch (msg) {
        case WM_CREATE:
            srand((unsigned int)time(NULL));
            init_node();
            init_edge();
            init_dmat();
            init_pb();
            return 0;
        case WM_DESTROY:
            delete_pb();
            PostQuitMessage(0);
            return 0;
        case WM_COMMAND:
            switch (LOWORD(wp)) {
                case BUTTON_START:
                    dijkstra();
                    InvalidateRect(hwnd,NULL,TRUE);
                    break;
                case BUTTON_RESET:
                    init_node();
                    init_edge();
                    init_dmat();
                    visible_edge = 1;
                    InvalidateRect(hwnd,NULL,TRUE);
                    break;
                case BUTTON_MINEDGE:
                    visible_edge = (visible_edge == 1) ? 0 : 1;
                    InvalidateRect(hwnd,NULL,TRUE);
                    break;
            }
        case WM_LBUTTONDOWN:
            pt.x = LOWORD(lp);
            pt.y = HIWORD(lp);
            if (SearchNode(pt))
                    InvalidateRect(hwnd,NULL,TRUE);
            break;
        case WM_PAINT:
            hdc = BeginPaint(hwnd , &ps);
            Draw_Node(hdc);
            if (visible_edge)
                Draw_Edge(hdc);
            Draw_MinEdge(hdc);

            EndPaint(hwnd , &ps);
            return 0;
    }
    return DefWindowProc(hwnd , msg , wp , lp);
}

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,
    PSTR lpCmdLine, int nCmdShow)
{
    HWND hwnd;
    MSG msg;
    WNDCLASS winc;

    winc.style    = CS_HREDRAW | CS_VREDRAW;
    winc.lpfnWndProc    = WndProc;
    winc.cbClsExtra     = 0;
    winc.cbWndExtra  = 0;
    winc.hInstance   = hInstance;
    winc.hIcon    = LoadIcon(NULL, IDI_APPLICATION);
    winc.hCursor       = LoadCursor(NULL, IDC_ARROW);
    winc.hbrBackground  = (HBRUSH)GetStockObject(WHITE_BRUSH);
    winc.lpszMenuName   = NULL;
    winc.lpszClassName  = TEXT("TEST");

    if (!RegisterClass(&winc))
        return -1;

    hwnd = CreateWindow(
        TEXT("TEST"), TEXT("Dijkstra"),
        (WS_OVERLAPPEDWINDOW ^ WS_THICKFRAME ^ WS_MAXIMIZEBOX) | WS_VISIBLE,
        CW_USEDEFAULT, CW_USEDEFAULT,
        WINDOW_WIDTH+9, WINDOW_HEIGHT+35,
        NULL, NULL, hInstance, NULL
    );

    if (hwnd == NULL)
        return -1;

    CreateWindow(
        TEXT("BUTTON") , TEXT("Start") ,
        WS_CHILD | WS_VISIBLE | BS_PUSHBUTTON ,
        WINDOW_WIDTH-80 , 2 , 80 , 23 ,
        hwnd , (HMENU)BUTTON_START , hInstance , NULL
    );

    CreateWindow(
        TEXT("BUTTON") , TEXT("Reset") ,
        WS_CHILD | WS_VISIBLE | BS_PUSHBUTTON ,
        WINDOW_WIDTH-80 , 27 , 80 , 23 ,
        hwnd , (HMENU)BUTTON_RESET , hInstance , NULL
    );

    CreateWindow(
        TEXT("BUTTON") , TEXT("Min edge") ,
        WS_CHILD | WS_VISIBLE | BS_PUSHBUTTON ,
        WINDOW_WIDTH-80 , 52 , 80 , 23 ,
        hwnd , (HMENU)BUTTON_MINEDGE , hInstance , NULL
    );

    while (GetMessage(&msg, NULL, 0, 0))
        DispatchMessage(&msg);

    return msg.wParam;
}