Whier

专注游戏开发，计算机图形图像
posts - 1, comments - 0, trackbacks - 0, articles - 0

2010年10月30日

Dijkstra Algorithm


算法描述参考：http://www.cnblogs.com/gzydn/archive/2009/07/09/1520019.html

// this program shows Dijkstra Algorithm
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char ** argv)
{
    int dis_metrix[5][5];
    bool is_in_s[5] = {false};
    int s[5];
    int dist[5] = {0};

    // init dis_metrix
    for(int m=0; m != 5; ++m)
        for(int n=0; n != 5; ++n)
            scanf("%d", &dis_metrix[m][n]);

    // init dist
    for (int m=0; m != 5; ++m)
        dist[m] = dis_metrix[0][m];
    is_in_s[0] = true;
    s[0] = 0;
    dist[0] = 0;

    // begin Dijkstra Algorithm
    int i, j, k;
    int t = 1;
    int max;
    for (k=1; k!=5; ++k)
    {
        // find the shortest path out of s
        max = 1000;
        for (i=0; i != 5; ++i)
        {
            if (is_in_s[i] == false && max > dist[i])
            {
                max = dist[i];
                t = i;
            }
        }
        is_in_s[t] = true;
        s[k] = t;
        // update shortest path
        for(j=0; j != 5; ++j)
        {
            if(is_in_s[j] == false && dist[j] > (dist[t] + dis_metrix[t][j]))
            {
                dist[j] = dist[t] + dis_metrix[t][j];
            }
        }
    }
}

posted @ 2010-10-30 12:21 whier 阅读(89) | 评论 (0) | 编辑 收藏