Floyd算法，求有向图中各顶点之间的最短路径及其长度

用Floyd算法实现求有向图中各顶点之间的最短路径及其长度

/*
  Name: Floyd算法
  Copyright: 
  Author:冰人
  Date: 22-11-08 13:42
  Description:实现Floyd算法，并求出有向图中各顶点之间的最短路径及其长度 
*/

#include 
#include 

using namespace std;

//函数结果状态码
#define OK    1
#define ERROR 0

//常量定义 
#define INFINITY 65535 //最大值 
#define MAXSIZE     20 //最大顶点个数
#define MAX        100

//Status是函数的类型，其值是函数结果状态代码
typedef int Status;

//----- 有向无环图的邻接矩阵表示法 -----
typedef struct {
    char vexs [MAXSIZE];            //顶点向量 
    int weight [MAXSIZE][MAXSIZE];  //邻接矩阵：用权值表示 
    int vexnum arcnum;             //图当前的顶点数和弧数 
} Graph;

//----- 最短路径存储结构 -----
typedef struct Path {
    int element;    //在头结点表示最短路径的长度，其他结点中表示最短路径中对应顶点的下标 
    struct Path *next;  
} Path;    

//函数功能：找到顶点在顶点向量中的下标
//返回值：若找到则返回此顶点在顶点向量中的下标，若没找到则返回-1 
int LocateVex （Graph G char v）
{
    int i;
    
    for （i = 0; i < G.vexnum; i ++）
        if （G.vexs [i] == v）   
            return i;          //若找到此顶点，则返回顶点对应的下标 
    
    return -1;                 //若没找到此顶点，则返回-1
}

//函数功能： 计算输入序列的长度并判断有没有顶点重复 
int countVexs （char * vertices）
{
	int i j;
	//先判断有输入的顶点没有重复  
	for （i = 0;i < MAX && vertices [i] != ‘\0‘;i ++）
	    for （j = i + 1;j < MAX && vertices [j] != ‘\0‘;j ++）
	        if （vertices [i] == vertices [j]）
	            return ERROR;     //若重复返回错误 
	
    for （i = 0;i < MAX && vertices [i] != ‘\0‘;i ++）;   //计算输入序列的长度
	return i;
}

//函数功能：用邻接矩阵表示法生成有向无环图 
Status CreateGraph （Graph &G）
{
    int i j k len;
    char v1 v2;
    char vertices [MAX];                 //储存输入的顶点 
    int occupy [MAXSIZE][MAXSIZE];       //标记邻接矩阵一条边是否已经存在
    
    do {
        cout << “请输入有向无环图的顶点数和弧数：“;
        cin  >> G.vexnum >> G.arcnum;
        if （G.vexnum <= 0 || G.vexnum > MAXSIZE || G.arcnum < 0 || G.arcnum > G.vexnum*（G.vexnum-1））
            cout << “输入不符合要求，请重新输入!!!“ << endl;
    } while （G.vexnum <= 0 || G.vexnum > MAXSIZE || G.arcnum < 0 || G.arcnum > G.vexnum*（G.vexnum-1））;
    
    //构造顶点向量
    do {
        cout << “请输入所有的顶点：“;
        cin  >> vertices;                //顶点向量先用一维数组vertices储存 
        len = countVexs （vertices）;      //计算输入的顶点向量的长度，并判断有没有输入的顶点重复 
        if （len != G.vexnum）             //若输入不符合要求，提示重新输入 
            cout << “输入不符合要求，请重新输入!!!“ << endl;
        else {                           //若输入符合要求，将这些顶点赋值给顶点向量 
            for （i = 0; i < G.vexnum; i ++） 
                G.vexs [i] = vertices [i];
        }
    } while （len != G.vexnum）;    
    
    //初始化邻接矩阵 
    for （i = 0; i < G.vexnum; i ++） 
        for （j = 0; j < G.vexnum; j ++） {
            G.weight [i][j] = INFINITY;  //弧的权值都赋值为无穷大
            occupy [i][j] = 0;           //弧的标记值都赋值为0 
        }
    
    //输入每一条弧依附的起点、终点和权值 
    for （k = 0; k < G.arcnum; k ++） {
        do {
            cout << “请输入第“ << k + 1 << “条弧的起点和终点：“;
            cin  >> v1 >> v2;
            i = LocateVex （G v1）;
            j = LocateVex （G v2）;            
            if （i == -1 || j

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       8563  2009-09-30 14:20  Floyd.cpp

----------- ---------  ---------- -----  ----

                 8563                    1