单源最短路径-Bellman-ford算法

本文主要是介绍单源最短路径-Bellman-ford算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

单源最短路径的求解方法主要有Bellman-Ford算法和Dijkstra算法，我会将两种算法的具体实现都写在博客里。两个算法的基本思想这里不赘述。本代码使用广度优先搜索和松弛算法来实现Bellman-Ford算法。Bellman-Ford算法是能对有权值为负的边的图进性判断能否得到最短路径的算法。
本代码中若是结果输出中有最短路径为负数的结果，就表示到该节点的距离为负无穷，及从源节点到该节点无法得到最短路径。
使用到的文件MapInfo.txt的内容如下：
s 6 t
s 7 y
t 5 x
t 8 y
t -4 z
y -3 x
y 9 z
x -2 t
z 2 s
z 7 x
左右两边的字符表示节点名称，中间的数字表示两个节点所在边的权值。
具体代码实现如下：

/** 单源最短路径：Bellman-ford算法* 这是一种基于广度优先搜索和松弛算法的单源最短路径求解方法*      author: StoryMonster*last change date: 2016/7/1*/
#include <iostream>
#include <stdlib.h>
#include <stdio.h>#ifndef TOTAL_NODES_IN_MAP
#define TOTAL_NODES_IN_MAP  5
#endif#define DEEP_MAX            10000
typedef struct MapNode
{int  deep;char NodeName;struct MapNode *father;
} MapNode;
typedef struct NeiborTable
{MapNode *node;int weight;                 //此处权值为表头节点与当前节点在网络中的权值struct NeiborTable *next;
} NeiborTable;NeiborTable *Head[TOTAL_NODES_IN_MAP];typedef struct NodeQueue
{NeiborTable *node;struct NodeQueue *next;
} NodeQueue;NodeQueue *QueueHead = (NodeQueue *)malloc(sizeof(NodeQueue));
int QueueSize = 0;static void         InitNeiborHeads(void);
static void         ReadConfigFile(void);
static void         InsertToNeiborTable(NeiborTable *, NeiborTable *);
static void         EnQueue(NeiborTable *);
static NeiborTable  *DeQueue(void);
static bool         QueueIsEmpty(void);
static void         BreadthFirstSearch(char);
static NeiborTable  *GetTheNeiborNode(char name);
static void         UpdateDeep(char, int);
static void         ShowAllShortestLength();void ShowAllShortestLength()
{for(int i=0;i<TOTAL_NODES_IN_MAP;i++){std::cout << (Head[i]->node)->NodeName<< ":"<<(Head[i]->node)->deep<<std::endl;}
}
void UpdateDeep(char name, int deep)
{for(int i=0;i<TOTAL_NODES_IN_MAP;i++){NeiborTable *p = Head[i];while(p != NULL){if((p->node)->NodeName == name){(p->node)->deep = deep;}p = p->next;}}
}
NeiborTable *GetTheNeiborNode(char name)
{for(int i=0;i<TOTAL_NODES_IN_MAP;i++){if((Head[i]->node)->NodeName == name){return Head[i];}}return NULL;
}void BreadthFirstSearch(char NodeName)
{NeiborTable *p = GetTheNeiborNode(NodeName);(p->node)->deep = 0;UpdateDeep((p->node)->NodeName,0);EnQueue(p);while(!QueueIsEmpty()){NeiborTable *u = DeQueue();if(u == NULL) break;NeiborTable *v = u->next;while(v != NULL){if((v->node)->deep < 0) ;else if(((u->node)->deep)+(v->weight) < (v->node)->deep ){(v->node)->deep = ((u->node)->deep)+(v->weight);UpdateDeep((v->node)->NodeName,(v->node)->deep);EnQueue(v);}else ;v = v->next;}}
}
bool QueueIsEmpty(void)
{if(QueueHead == NULL) return true;return false;
}
NeiborTable *DeQueue()
{if(QueueIsEmpty()) return NULL;QueueSize--;NodeQueue *p = QueueHead;QueueHead = QueueHead->next;for(int i=0;i<TOTAL_NODES_IN_MAP;i++){if((Head[i]->node)->NodeName == ((p->node)->node)->NodeName){free(p);p = NULL;return Head[i];}}return NULL;
}
void EnQueue(NeiborTable *node)
{QueueSize++;if(QueueHead == NULL){NodeQueue *head = (NodeQueue *)malloc(sizeof(NodeQueue));head->node = node;head->next = NULL;QueueHead  = head;return ;}NodeQueue *p = QueueHead;NodeQueue *NewNode = (NodeQueue *)malloc(sizeof(NodeQueue));NewNode->node = node;NewNode->next = NULL;while(p->next != NULL) p = p->next;p->next = NewNode;
}
void InsertToNeiborTable(NeiborTable *head, NeiborTable *table)
{int index = 0;while(Head[index] != NULL){if((Head[index]->node)->NodeName == (head->node)->NodeName){NeiborTable *p = Head[index];while(p->next != NULL) p = p->next;p->next = table;free(head);head = NULL;return ;}index++;}Head[index] = head;Head[index]->next = table;
}
void InitNeiborHeads(void)
{for(int i=0;i<TOTAL_NODES_IN_MAP;i++){Head[i] = (NeiborTable *)malloc(sizeof(NeiborTable));Head[i] = NULL;}
}
void ReadConfigFile(void)
{FILE *fp = fopen("MapInfo.txt","rb");if(!fp){std::cout << "Open MapInfo.txt fail!"<<std::endl;fp = NULL;return ;}while(1){int weight = 0;char name1 = 0,name2 = 0;int n = fscanf(fp,"%c %d %c\n",&name1,&weight,&name2);if(n < 1) break;NeiborTable *table1 = (NeiborTable *)malloc(sizeof(NeiborTable));NeiborTable *table2 = (NeiborTable *)malloc(sizeof(NeiborTable));MapNode *node1 = (MapNode *)malloc(sizeof(MapNode));MapNode *node2 = (MapNode *)malloc(sizeof(MapNode));node1->deep = DEEP_MAX;node1->NodeName = name1;node2->deep = DEEP_MAX;node2->NodeName = name2;table1->weight = 0;table2->weight = weight;table1->next = NULL;table2->next = NULL;table1->node = node1;table2->node = node2;InsertToNeiborTable(table1,table2);}fclose(fp);fp = NULL;
}
void ShowNeiborTable(void)
{std::cout << "Show neibor table"<<std::endl;for(int i=0;i<TOTAL_NODES_IN_MAP;i++){NeiborTable *p = Head[i];while(p != NULL){std::cout <<(p->node)->NodeName << p->weight << "  ";p = p->next;}std::cout << std::endl;}
}
int main()
{QueueHead = NULL;InitNeiborHeads();ReadConfigFile();BreadthFirstSearch('s');//ShowNeiborTable();ShowAllShortestLength();return 0;
}