dijsktra2

dijsktra.c

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

static int getCost( side* sideList, int s, int e );

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

int dijsktra( int n, side* sideList, int startIdx, int goalIdx, int **route, int* totalCost ){
	/* メモリ確保 */
	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( getCost(sideList, fix, i) != INT_MAX
				&& vertexes[ i ].isFixed == 0 ) {

				if( vertexes[ i ].minCost > vertexes[ fix ].minCost + getCost( sideList, fix, i ) ) {
					/* 確定頂点を経由するルートの方がよりコストが少ないか */
					vertexes[ i ].minCost = vertexes[ fix ].minCost + getCost( sideList, 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;
	*totalCost = 0;
	for( int i = n - 1; i >= 0; i-- ) {
		if( tmp[ i ] != -1 ) {
			( *route )[ j++ ] = tmp[ i ];
		}
	}

	for( int i = 0; i < n -1; i++ ) {
		if( (*route)[ i + 1 ] != -1 ) {
			*totalCost = *totalCost + getCost( sideList, ( *route )[ i ], ( *route )[ i + 1]);
		}
	}

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

static int getCost( side* sideList, int s, int e ) {
	side* t;
	for( t = &( sideList[ 0 ] ); t != NULL; t = t->next ) {
		if( t->s == s && t->e == e ) {
			return t->c;
		}
	}
	return INT_MAX;
}

dijsktra.h

#pragma once

/* 辺 */
typedef struct _side side;
struct _side {
	int s;	/* 始まり */
	int e;	/* 終わり */
	int c;	/* コスト */
	struct side* next;
};

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

  @param n 頂点数
  @param sideList 辺リスト
  @param startIdx スタート頂点
  @param goalIdx ゴール頂点
  @param route 最短ルート
  @param totalCost 最短ルートコスト
  @return 成否(0:成功、-1:失敗)
*/
int dijsktra( int n, side* sideList, int startIdx, int goalIdx, int **route, int* totalCost );

test_dijsktra.c

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

void test1() {
	int n = 7;	/* 全頂点数 */
	int sideNum = 22;	/* 全辺数 */

	side* sideList = ( side* )malloc( sizeof( side ) * sideNum );
	/* 0 */
	sideList[ 0 ].s = 0; sideList[ 0 ].e = 1; sideList[ 0 ].c = 2;
	sideList[ 1 ].s = 0; sideList[ 1 ].e = 2; sideList[ 1 ].c = 4;
	/* 1 */
	sideList[ 2 ].s = 1; sideList[ 2 ].e = 0; sideList[ 2 ].c = 2;
	sideList[ 3 ].s = 1; sideList[ 3 ].e = 2; sideList[ 3 ].c = 1;
	sideList[ 4 ].s = 1; sideList[ 4 ].e = 3; sideList[ 4 ].c = 3;
	sideList[ 5 ].s = 1; sideList[ 5 ].e = 4; sideList[ 5 ].c = 5;
	/* 2 */
	sideList[ 6 ].s = 2; sideList[ 6 ].e = 0; sideList[ 6 ].c = 4;
	sideList[ 7 ].s = 2; sideList[ 7 ].e = 1; sideList[ 7 ].c = 1;
	sideList[ 8 ].s = 2; sideList[ 8 ].e = 5; sideList[ 8 ].c = 3;
	/* 3 */
	sideList[ 9 ].s = 3; sideList[ 9 ].e = 1; sideList[ 9 ].c = 3;
	sideList[ 10 ].s = 3; sideList[ 10 ].e = 4; sideList[ 10 ].c = 1;
	sideList[ 11 ].s = 3; sideList[ 11 ].e = 6; sideList[ 11 ].c = 6;
	/* 4 */
	sideList[ 12 ].s = 4; sideList[ 12 ].e = 1; sideList[ 12 ].c = 5;
	sideList[ 13 ].s = 4; sideList[ 13 ].e = 3; sideList[ 13 ].c = 1;
	sideList[ 14 ].s = 4; sideList[ 14 ].e = 5; sideList[ 14 ].c = 1;
	sideList[ 15 ].s = 4; sideList[ 15 ].e = 6; sideList[ 15 ].c = 4;
	/* 5 */
	sideList[ 16 ].s = 5; sideList[ 16 ].e = 2; sideList[ 16 ].c = 3;
	sideList[ 17 ].s = 5; sideList[ 17 ].e = 4; sideList[ 17 ].c = 1;
	sideList[ 18 ].s = 5; sideList[ 18 ].e = 6; sideList[ 18 ].c = 2;
	/* 6 */
	sideList[ 19 ].s = 6; sideList[ 19 ].e = 3; sideList[ 19 ].c = 6;
	sideList[ 20 ].s = 6; sideList[ 20 ].e = 4; sideList[ 20 ].c = 4;
	sideList[ 21 ].s = 6; sideList[ 21 ].e = 5; sideList[ 21 ].c = 2;

	for( int i = 0; i < sideNum - 1; i++ ){
		sideList[ i ].next = &( sideList[ i + 1 ] );
	}
	sideList[ sideNum - 1 ].next = NULL;

	
	int *ret = NULL;
	int totalCost;
	dijsktra(n, sideList, 0, 6, &ret, &totalCost);

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


	ret = NULL;
	dijsktra( n, sideList, 0, 4, &ret, &totalCost );

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

int main() {
	test1();
	return 0;
}