bellmanford.h

bellman-ford的实现。可以输出每条最短路径经过的节点

 #ifndef ALGRAPH_H
 #define ALGRAPH_H
 #include<iostream>

 
using namespace std;

#define max 65535      //初始权值无穷大

typedef enum {WHITE,GRAY,BLACK};

typedef struct VNode VNode;

typedef struct ArcNode
{
    int         adjvex;  /**//* 原顶点 */
    ArcNode*    nextarc;    /**//* 指向下一条弧的指针 */
    long        weight;  /**//* 权值 */
}ArcNode;                    /**//* 表结点 */


typedef struct VNode
{    
    int        adjvex;           /**//* 顶点序号    */
    char        value;            /**//* 顶点颜色    */
    long        d;               /**//* 顶点最初DFS发现时间 ; 兼作Dijkstra算法中当前最短路径 */
    VNode *     father;
    ArcNode *   firstarc;         /**//* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */
}VNode,* AdjList ; /**//* 头结点 */


typedef struct
{
    AdjList vertices;                /**//* 表结点指针(一个头结点数组) */
    int     vexnum,arcnum;           /**//* 图的当前顶点数和弧数 */
}ALGraph;

#endif