#include <stdio.h>
#include <stdlib.h>
#define ERROR_NO_MEM -1 /*内存不足的错误码*/
#define MAX_POINT_NUM 5 /*最大的点数*/
#define MAX_EDGE_NUM 7 /*最多的边数*/
#define MAX_VALUE 0xfffffff /*最大路径长度*/
/*表示每个结点的信息*/
struct tagEdgeNode
{
int value; /*结点数值*/
struct tagEdgeNode *next; /*指向路径的下一个结点*/
};
/*存储路径的数组*/
typedef struct tagEdgeNode *adjlist[MAX_POINT_NUM];
/*存储图的邻接矩阵*/
typedef int AdjMatrix[MAX_POINT_NUM ][MAX_POINT_NUM ];
/*
释放链表上的动态内存
*/
void freeNode(struct tagEdgeNode *list)
{
struct tagEdgeNode *p = NULL;
struct tagEdgeNode *tmp = NULL;
p = list;
while(NULL != p)
{
tmp = p->next;
free(p);
p = tmp;
}
return ;
}
/*
显示图的邻接矩阵
*/
void showGraph(AdjMatrix GA)
{
int i;
int j;
for(i = ; i < MAX_POINT_NUM; i++)
{
for(j = ; j < MAX_POINT_NUM; j++)
{
if(( MAX_VALUE != GA[i][j] ) && ( != GA[i][j] ))
{
printf("GA[%d][%d] =%d \r\n", i, j, GA[i][j]);
}
}
printf("\r\n");
}
return ;
}
/*
修改路径结点
*/
int ChangePath(adjlist path, int m, int j)
{
struct tagEdgeNode *p = NULL;
struct tagEdgeNode *q = NULL;
struct tagEdgeNode *end = NULL;
/*清除顶点j的当前最短路径*/
freeNode(path[j]);
path[j] = NULL;
/*把到顶点m的最短路径复制到顶点j的最短路径上*/
p = path[m];
while(NULL != p)
{
q = malloc(sizeof(struct tagEdgeNode));
if(NULL == q)
{
/*申请内存失败，释放已有链表*/
freeNode(path[j]);
return ERROR_NO_MEM;
}
q->value = p->value;
if( NULL == path[j] )
{
path[j] = q;
}
else
{
end->next = q;
}
end = q;
p = p->next;
}
/*把顶点j加入到path[j]单链表的最后，形成新的目前最短路径*/
q = malloc(sizeof(struct tagEdgeNode));
if(NULL == q)
{
/*申请内存失败，释放已有链表*/
freeNode(path[j]);
return ERROR_NO_MEM;
}
q->value = j;
q->next = NULL;
end->next = q;
return ;
}
/*
查找出从节点i开始到其他所有节点的最短路径(dijkstra算法)
*/
int FindShortestPath(AdjMatrix GA, int dist[], adjlist path, int i)
{
int j, k,w,m;
int newDistance;
int minDistance;
int Set[MAX_POINT_NUM]; /*存放已求得最短路径的节点*/
struct tagEdgeNode *p1 = NULL;
struct tagEdgeNode *p2 = NULL;
/*初始化Set集合、路径结点集合*/
for(j =; j < MAX_POINT_NUM; j++)
{
if( j == i )
{
Set[j] = ;
}
else
{
Set[j] = ;
}
dist[j] = GA[i][j];
/*如果到相邻结点的距离不是无穷大，则记录该路径*/
if(( dist[j] < MAX_VALUE ) && ( j != i))
{
p1 = malloc(sizeof(struct tagEdgeNode));
p2 = malloc(sizeof(struct tagEdgeNode));
if(( NULL == p1) || ( NULL == p2 ))
{
if( NULL != p1 )
{
free(p1);
}
if( NULL != p2 )
{
free(p2);
}
return ERROR_NO_MEM;
}
p1->value = i;
p2->value = j;
p2->next = NULL;
p1->next = p2;
path[j] = p1;
}
else
{
path[j] = NULL;
}
}
/*共计需要n-2次循环, 每次循环选择路径最短的作为起点*/
for ( k = ; k <= MAX_POINT_NUM-; k++)
{
/*求出第k个终点m*/
minDistance = MAX_VALUE;
m = i;
/*寻找到下一个开始搜寻的节点：条件是不在集合中，而且距起始节点最近*/
for(j = ; j < MAX_POINT_NUM; j++)
{
if(( Set[j] == ) && (dist[j] < minDistance))
{
minDistance = dist[j];
m = j;
}
}
/*若条件成立, 则把顶点m并入集合S中, 否则退出循环,因为剩余的顶点,
其最短路径长度均为MAX_VALUE,无需再计算*/
if( m != i)
{
Set[m] = ;
}
else
{
break;
}
/*从未排序节点中选择对应dist和path中的元素做必要修改*/
for( j = ; j < MAX_POINT_NUM; j++)
{
newDistance = dist[m] + GA[m][j];
if(( == Set[j] ) && ( newDistance < dist[j] ))
{
dist[j] = newDistance;
ChangePath(path, m, j);
}
}
}
/*显示图的最短距离和最短路径*/
printf("next show shortest path as following: \r\n");
for(i = ; i < MAX_POINT_NUM; i++)
{
printf("min distance to [%d] = %d \r\n", i, dist[i]);
printf("path:");
p1 = path[i];
while(NULL != p1)
{
printf(" %d ", p1->value);
p1 = p1->next;
}
printf("\r\n\r\n");
}
/*释放所有的动态内存*/
for(i = ; i < MAX_POINT_NUM; i++)
{
freeNode(path[i]);
}
return ;
}
/*
创建图的邻接矩阵。
创建成功时，返回0.
创建失败时，返回错误码
*/
int createGraph(AdjMatrix GA)
{
int i;
int j;
int k;
int weigt;
/*初始化邻接数组*/
for(i = ; i < MAX_POINT_NUM; i++)
{
for(j = ; j < MAX_POINT_NUM; j++)
{
if( i == j)
{
GA[i][j] = ;
}
else
{
GA[i][j] = MAX_VALUE;
}
}
}
/*建立邻接数组*/
printf("input number from 0 to 4 as edge point. and max 7 link between those points. weigt should less than 0xfffffff\r\n");
printf("input one edge, from i to j, weigh, format is: i j weigt \r\n");
for(k = ; k <= MAX_EDGE_NUM; k++ )
{
/*建立一条边。从i到j. 权值为w <i j w>*/
scanf("%d %d %d", &i, &j, &weigt);
/*判断参数合法性*/
if(( i > ) || ( j > ) || (weigt >= MAX_VALUE))
{
printf("invalid i or j or weigt value. i=%d j=%d weigt=%d \r\n", i, j, weigt);
continue;
}
GA[i][j] = weigt;
}
/* 可以用下面这组作为测试数据，验证算法
GA[0][1] = 1;
GA[0][2] = 2;
GA[1][2] = 3;
GA[1][3] = 1;
GA[1][4] = 3;
GA[3][4] = 1;
GA[2][4] = 2;
*/
return ;
}
int main()
{
int ret;
AdjMatrix GA;
adjlist path;
int dist[MAX_POINT_NUM];
ret = createGraph(GA);
if( != ret)
{
printf("error. fail to create Graph");
return ;
}
showGraph(GA);
ret = FindShortestPath(GA, dist, path, );
if( != ret)
{
printf("error. can not find the short path from point 0 in Graph");
return ;
}
return ;
}