test.c

求单源点最短路径算法

/*============================单源点最短路径算法===========================*/
/*   该算法为产生最短路径的贪心算法，对一个给定的带权图，用邻接矩阵存储    */
/*   顶点信息和顶点之间的权值，不向相邻的顶点之间的权值设为最大的整数32766 */
/*   代表无穷值，然后按照Dijkstra算法的思想按路径长度递增的顺序依次找出原点*/
/*   到各顶点的最短路径，主要的操作是对矩阵进行操作，其中另设一个存储顺序找*/
/*   到的各个顶点，这些顶点到源点的路径长度是递增的。                      */
#include <stdio.h>         /*头文件包含*/
#include <stdlib.h>
#include <bios.h>

#define MAX 100            /*预置矩阵的大小，也即顶点数的最大值*/


typedef struct waynode{    /*顶点信息数据结构，只需包含该顶点的名称*/
    char name[ 10 ];
    struct waynode * next;
    }WAYNODE;

typedef struct store{     /* 数据信息的概括所用的数据结构 */
    int  MAXv;            /* 顶点数*/
    int  MAXe;            /* 编边数*/
    WAYNODE first[MAX];   /* 存储顶点的结点数组*/
    }STORE;


int  check( struct store * head, char * string )      /* 对输入的顶点进行检查，看是否属于顶点集，参数为存储顶点结构的执指针和输入的顶点值*/
{                                                     /* 作为返回的位置*/
    int key;
    for( key = 0; key < head -> MAXv; key++ )
    {
        if( ( strcmp( (*head).first[key].name, string ) ) == 0 )     /*找到输入的顶点，即输入的顶点在顶点集合中，返回其在顶点集合中的位置*/
            return(key);
    }
    if( key == head -> MAXv )                                        /*没找到返回－1*/
      return( -1 );
}


int getkey ( )
{
    union  star
    {
       unsigned int x;
       unsigned char y[2];
    }key1;
    do
    {
        key1.x = bioskey( 0 );
        return ( key1.y[1] );
    }while ( 1 );
}
    
void main ( )
{
    int  i, j, k,checkmark1, checkmark2, input1 = 0, input2 = 0, min=0;  /*变量的定义checkmark1,checkmark2分别作为返回顶点位置的标标识量，input1,input2是输入信息检查的控制量 */
    int  shortcut, line[MAX], mark, key,exist,answer = 1;              /*shortcut是最短的路径长度，line[]数组存放依次找到的顶点，mark是每次找到的顶点在顶点集合中的位置