dijsktra

dijsktra.c

#include <stdlib.h>
#include <string.h>
#include <limits.h> 


/* 頂点 */
typedef struct vertile_tag {
	int isFixed;		/* 1:確定、0:未確定 */
	int minCost;		/* 最低必要コスト */
	int prev;		/* 直前頂点 */
}vertex;


int dijsktra( int n, int** cost, int startIdx, int goalIdx, int **route ) {
	/* メモリ確保 */
	vertex* vertexes = malloc( sizeof( vertex ) * n );
	if( vertexes == NULL ) {
		return -1;
	}
	memset( vertexes, 0x00, sizeof( vertexes ) );

	/* 初期化 */
	for( int i = 0; i < n; i++ ) {
		vertexes[ i ].minCost = INT_MAX;
		vertexes[ i ].isFixed = 0;
		vertexes[ i ].prev = -1;
	}

	/* スタート設定 */
	vertexes[ startIdx ].minCost = 0;

	while( vertexes[ goalIdx ].isFixed != 1 ) {	/* ゴール頂点が確定するまで */
		/* 未確定で、コスト最小頂点を確定済みとする */
		int fix;	/* 確定頂点 */
		int min = INT_MAX;
		for( int i = 0; i < n; i++ ) {
			if( vertexes[ i ].isFixed == 0 ) {
				if( min > vertexes[ i ].minCost ) {
					min = vertexes[ i ].minCost;
					fix = i;
				}
			}
		}
		vertexes[ fix ].isFixed = 1;

		/* 確定頂点とつながっている未確定頂点を更新 */
		for( int i = 0; i < n; i++ ) {
			if( cost[ fix ][ i ] != INT_MAX
				&& vertexes[ i ].isFixed == 0 ) {

				if( vertexes[ i ].minCost > vertexes[ fix ].minCost + cost[ fix ][ i ] ) {
					/* 確定頂点を経由するルートの方がよりコストが少ないか */
					vertexes[ i ].minCost = vertexes[ fix ].minCost + cost[ fix ][ i ];
					vertexes[ i ].prev = fix;
				}
			}
		}
	}

	/* 戻り値作成 */
	int *tmp = NULL;
	tmp = malloc( sizeof( int ) * n );
	if( tmp == NULL ) {
		return -1;
	}
	int i = 0;
	for( i = 0; i < n; i++ ) {
		tmp[ i ] = -1;
	}

	vertex t;
	t = vertexes[ goalIdx ];
	tmp[ 0 ] = goalIdx;
	i = 1;
	while( t.prev != -1 ) {
		tmp[ i++ ] = t.prev;
		t = vertexes[ t.prev ];
	}


	*route = malloc( sizeof( int ) * n );
	if( tmp == NULL ) {
		return -1;
	}
	for( int j = 0; j < n; j++ ) {
		( *route )[ j ] = -1;
	}

	int j = 0;
	for( int i = n - 1; i >= 0; i-- ) {
		if( tmp[ i ] != -1 ) {
			( *route )[ j++ ] = tmp[ i ];
		}
	}

	free( vertexes );
	free( tmp );
	vertexes = NULL;
	return 0;
}

dijsktra.h

#pragma once

/*
　最短ルートを求める。
  routeはn要素数の配列。ゴール頂点以降は各要素に-1が入る。
  また、呼び出し側で解放要。

  @param n 頂点数
  @param cost 各頂点間コスト(隣接行列)
  @param startIdx スタート頂点
  @param goalIdx ゴール頂点
  @param route 最短ルート
  @return 成否(0:成功、-1:失敗)
*/
int dijsktra( int n, int** cost, int startIdx, int goalIdx, int **route );

test_dijsktra.c

#include <stdlib.h>
#include <stdio.h>
#include "dijsktra.h"

void test1() {
	int n = 7;

	int cost[ 7 ][ 7 ] = {
		{ INT_MAX,	2,		4,		INT_MAX,	INT_MAX,	INT_MAX,	INT_MAX	},
		{ 2,			INT_MAX,	1,		3,		5,		INT_MAX,	INT_MAX	},
		{ 4,			1,		INT_MAX,	INT_MAX,	INT_MAX,	3,		INT_MAX	},
		{ INT_MAX,	3,		INT_MAX,	INT_MAX,	1,		INT_MAX,	6		},
		{ INT_MAX,	5,		INT_MAX,	1,		INT_MAX,	1,		4		},
		{ INT_MAX,	INT_MAX,	3,		INT_MAX,	1,		INT_MAX,	2		},
		{ INT_MAX,	INT_MAX,	INT_MAX,	6,		4,		2,		INT_MAX	}
	};

	int *cost2[ 7 ];
	for( int i = 0; i < n; i++ ) {
		cost2[ i ] = cost[ i ];
	}

	int *ret = NULL;

	dijsktra(7, cost2, 0, 6, &ret);

	for( int i = 0; i < n; i++ ) {
		if( ret[ i ] != -1){
			printf( "%d", ret[ i ] );
		}
	}
	printf( "\n" );
	free( ret );
}

void test2() {
	int n = 7;

	int cost[ 7 ][ 7 ] = {
		{ INT_MAX,	2,		4,		INT_MAX,	INT_MAX,	INT_MAX,	INT_MAX },
		{ 2,			INT_MAX,	1,		3,		5,		INT_MAX,	INT_MAX },
		{ 4,			1,		INT_MAX,	INT_MAX,	INT_MAX,	3,		INT_MAX },
		{ INT_MAX,	3,		INT_MAX,	INT_MAX,	1,		INT_MAX,	6 },
		{ INT_MAX,	5,		INT_MAX,	1,		INT_MAX,	1,		4 },
		{ INT_MAX,	INT_MAX,	3,		INT_MAX,	1,		INT_MAX,	2 },
		{ INT_MAX,	INT_MAX,	INT_MAX,	6,		4,		2,		INT_MAX }
	};

	int *cost2[ 7 ];
	for( int i = 0; i < n; i++ ) {
		cost2[ i ] = cost[ i ];
	}

	int *ret = NULL;

	dijsktra( 7, cost2, 0, 4, &ret );

	for( int i = 0; i < n; i++ ) {
		if( ret[ i ] != -1 ) {
			printf( "%d", ret[ i ] );
		}
	}
	printf( "\n" );
	free( ret );
}

int main() {

	test1();
	test2();

	return 0;
}