shortestpath.h

算法实验:1 分治法在数值问题中的应用 ——最近点对问题 2 减治法在组合问题中的应用——8枚硬币问题 3 变治法在排序问题中的应用——堆排序 4 动态规划法在图问题中的应用——全源最短路径问题

#pragma once
#ifndef SHORTESTPATH_H
#define SHORTESTPATH_H

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <limits.h>
#include <math.h>
#include <string.h>

#define FILE_OPEN_ERROR	 1
#define INFINITY    INT_MAX  //最大值∞
#define MAX_VERTEX  20
#define MAX_NAME    5
typedef int Arcs[MAX_VERTEX][MAX_VERTEX];//邻接矩阵
typedef char VertexType[MAX_NAME];


//==========================================================
//弗洛伊德算法
typedef struct{
	VertexType path;
}PthMatrix[MAX_VERTEX][MAX_VERTEX];
typedef int DistancMatrix[MAX_VERTEX][MAX_VERTEX];
//==========================================================

typedef struct{//Digetwork Data structure
	VertexType	vexs[MAX_VERTEX];	//Vertexs Set
	Arcs		arcs;				//Arc Adjacency Matrix
	int			vexnum;				//total of vertex
	int			arcnum;				//total of arc
}DNetwork;

//create a Dignetwork,get the infomations from file
void CreateDN(DNetwork *G,const char vexinfo[],const char arcinfo[]);

//Output the infomation
void OutputDN(DNetwork G);


//get the location of v0 in the DNetwork
int VexLocation(DNetwork G,VertexType v0);

/*===============================================================
 *用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其
 * 带权长度D[v][w]。若P[v][w][u]为TRUE,则u是从v到w当前求得最短
 * 路径上的顶点。算法7.16 
 *  typedef int PthMatrix[MAX_VERTEX][MAX_VERTEX][MAX_VERTEX];
 *  typedef int DistancMatrix[MAX_VERTEX][MAX_VERTEX];
 *  ShortestPath_FLOYD()要求对角元素值为0 
 *===============================================================*/
void ShortestPath_FLOYD(DNetwork G,PthMatrix *P,DistancMatrix *D);

void PathStart();


#endif SHORTESTPATH_H