单源点最短路径Bellman算法实现

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

一、数据集形式

其中：6105（节点个数） 7035（边数）
0（id） 1609（起始边） 1622（终边） 57.403187（权重）

二、数据集

数据集下载链接

三、实现代码

#include "stdafx.h"
#include "time.h"
#include <fstream>
#include<iostream>
#include <stack>
#include <queue>
#include<algorithm>
using namespace std;
int nodeNumber;
int edgeNumber;#define PATH "E://dataset//MapSet//MinCreateTree//Testnew.txt"//#define PATH "E://dataset//MapSet//MinCreateTree//Ol.txt"
//#define PATH "E://dataset//MapSet//MinCreateTree//TGRoad.txt"
//#define PATH "E://dataset//MapSet//MinCreateTree//California.txt"
//#define PATH "E://dataset//MapSet//MinCreateTree//San.txt"
//#define PATH "E://dataset//MapSet//MinCreateTree//NA.txt"
class CTreeNode
{
public:CTreeNode(){}~CTreeNode() {}int value;double  weight;CTreeNode *next;
};
class CTree
{
public:CTree() {weight = 65535;}~CTree() {}int value;CTreeNode *next;CTree *before;double weight;
};
CTree* createTree(char* filename)
{CTree *tree;ifstream ReadFile;int temp;ReadFile.open(filename, ios::in);//ios::in 表示以只读的方式读取文件ReadFile >> nodeNumber;//第一个字符是数组长度ReadFile >> edgeNumber;tree = new CTree[nodeNumber];//为树赋初值for (int i = 0; i < nodeNumber; i++){tree[i].next = NULL;tree[i].value = i;tree[i].before = NULL;}tree[0].weight = 0;CTreeNode *nt;while (!ReadFile.eof())            //按空格读取，遇到空白符结束{nt = new CTreeNode();       //读出的数据新建一个节点ReadFile >> temp;ReadFile >> temp;ReadFile >> (nt->value);ReadFile >> (nt->weight);nt->next = tree[temp].next;tree[temp].next = nt;}return tree;
}
queue<CTree *> myQ;
void Bellman(CTree *t, CTree *tree)
{CTreeNode *p = t->next;while (p!=NULL){//链接的节点已经完成，不做任何改变if (t->weight!=65535&&tree[p->value].weight>t->weight+p->weight){//cout << tree[p->value].value << " ";tree[p->value].weight = t->weight + p->weight;tree[p->value].before = t;//Bellman(tree, p->value);myQ.push(&tree[p->value]);}p = p->next;}
}
void Bell(CTree *tree)
{myQ.push(&tree[0]);while (!myQ.empty()){Bellman(myQ.front(),tree);myQ.pop();}
}
int main()
{//构建图CTree *tree = createTree(PATH);double useTime;clock_t start, finish;start = clock();//算法Bell(tree);finish = clock();useTime = (double)(finish - start) / CLOCKS_PER_SEC * 1000;printf("%f 毫秒\n", useTime);system("pause");return 0;
}

这篇关于单源点最短路径Bellman算法实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---