shortestpath.c

图的用法

#include<stdlib.h>
#include<stdio.h>
#define SIZE 100
#define MAXLEN  1000      //最长可能距离
int **node;               //保存用户输入的数据（起点。终点。权值）
int cost[SIZE][SIZE];     //保存权值
int dist[SIZE];              //路径长度数组
struct node               //图的顶点结构
{
	int vertex;           //顶点数据
	struct node *nextnode;
};
typedef struct node *graph;        //图的结构新类型
struct node head[9];               //图顶点结构数组
int visited[9];                    //遍历记录数组


/* --------------------------*/
/* create the JiaQuan graph  */
/* --------------------------*/
void creategraph(int **node,int num)
{
	int from;                //边的起点
	int to;                  //边的终点
	int i;
	for(i = 0;i < num;i++)    //读取边的循环
	{
		from = node[i][0];                               //边的起点
		to = node[i][1];                             //边的终点
		cost[from][to] = node[i][2];
	}
}



/* --------------------------*/
/*   find the shortest path  */
/* --------------------------*/

void shortestpath(int begin,int num)
{
	int selected[SIZE];                          //选择顶点数组
	int min;                                     //最短距离
	int s;                                       //最短距离的顶点
	int i,j;

	for(i = 2;i <= num;i++)                      //初始数组循环
	{
		selected[i] = 0;                         //清楚数组内容
		dist[i] = cost[begin][i];                //初始数据
	}
	selected[begin] = 1;                         //设置找过开始顶点
	dist[begin] = 0;                             //设置开始定点距离
	printf("1    2    3     4     5     6 \n");
	for(j=1;j<=num;j++)                          //输出初始数组内容
	{
		printf("%d  ",dist[j]);                   //输出距离
	}
	printf("\n");
	for(i=1;i<=num-1;i++)
	{
		min = MAXLEN;                              //先设为最长距离
		for(j=1;j<=num;j++)
			if(min > dist[j] && selected[j] == 0)
			{
				s = j;                             //目前最短的顶点
				min = dist[j];                     //记录最短距离
			}
		selected[s] = 1;                           //设置应经找过

		for(j=1;j<=num;j++)
		{
			if(selected[j] == 0 && (dist[s] + cost[s][j]) < dist[j])    //是否比较短
				dist[j] = (dist[s] +cost[s][j]);   //设为最短距离
			printf("%d  ",dist[j]);		           //输出最短距离
		}
		printf("\n");

	}
}

/* --------------------------*/
/*      the main fuction     */
/* --------------------------*/

void main()
{
	int i,j;
	int x,y;              //记录从哪点到哪点的最短路径
	int m,n=3;            //控制动态二维数据的声请

	clrscr();
	/* 建立二维数组保存用户的输入：包括（起点，终点，以及权值）*/
	printf("Please input one number:\n");
	scanf("%d",&m);
	node = (int **) malloc(m*sizeof(int *));
	for(i = 0;i < m;i ++)
		node[i] = (int *)malloc(n*sizeof(int));
	for(i = 0;i < m;i ++)
		{
			printf("Please input datas:\n");
			scanf ("%d,%d,%d",&node[i][0],&node[i][1], &node[i][2]) ;
		}
	for(i = 1;i <= 6;i++ )
	for(j = 1;j <=6;j++)
		cost[i][j] = MAXLEN;                     //    设置数组最长距离
    creategraph(node,m);
	printf("\ninput the two points:\n");
	scanf("%d %d",&x,&y);
	shortestpath(x,y);                             //查找最短路径
}