用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - c++代码库

单源最短路径 (迪杰斯特拉算法)

2016-09-13 作者: 小维天使001举报

[c++]代码库

// DijstraAlgorithm.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;
//const变量声明
const int N = 20;
const int INFTY = 65536;
//结构体预先定义
struct sNode{
	int dis;
	int pre;
	int flag;
};
/*功能函数声明定义*/
/*初始化city函数*/
void Init( int (*city)[N],int iCity){
	//init - city[][]
	for(int i=0; i<iCity; i++){
		for(int j=0; j<iCity; j++){
			if(i == j)	
				city[i][j] = 0;
			else
				city[i][j] = INFTY;
		}
	}
	return;
}
/*输入函数,用于输入城市之间的距离,也就是有向图的边,用邻接矩阵表示*/
void Input(int (*city)[N], int iEdge){
	Init(city,N);
	int x, y;
	for(int i=0; i<iEdge; i++){
		cin >> x >> y ;
		cin >> city[x][y];
	}

	return;
}
/*选择当前为标记的点的最小边*/
int ChooseEdge( int (*city)[N], sNode point[], int iCity ){
	int minPoint = -1, minEdge = INFTY;
	for(int i=0; i<iCity; i++){
		if(minEdge > point[i].dis && point[i].flag == 0){
			minEdge = point[i].dis;
			minPoint = i;
		}
	}
	return minPoint;
}
/*地接斯特拉算法,核心*/
void Dijstra( int (*city)[N], sNode point[], int iCity ){
	/* 初始化 struct sNode  point[] */
	int Source = 0; 
	for(int i=0; i<iCity; i++){
		point[i].dis = city[Source][i];
		point[i].flag = 0;
		if( i != Source && city[Source][i] < INFTY )
			point[i].pre = Source;
		else
			point[i].pre = -1;
	}
	/* 将源点加入 */
	point[Source].flag = 1;
	/* 开始循环 */
	for(int i=0; i<iCity-1; i++){
		int k = 0;
		k = ChooseEdge(city, point, iCity);
		if(k == -1)
			break;
		point[k].flag = 1;
		for(int j=0; j<iCity; j++){
			int temp = point[k].dis + city[k][j];
			if( point[j].flag == 0 && temp<point[j].dis){
				point[j].dis = temp;
				point[j].pre = k;
			}
		}
			//
		for(int x=0;x<iCity;x++) //详细过程;
			cout << point[x].dis << "," << point[x].pre << "\t";
		cout << endl;
		//
	}
	return;
}
//进入main函数
int main(int argc, char* argv[])
{
	int city[N][N];
	/*struct*/ sNode point[N];
	int iCity = 0, iEdge = 0;
	cin >> iCity;
	cin >> iEdge;
	//start
	Init( city, iCity );
	Input( city, iEdge );
	Dijstra( city, point, iCity );
	return 0;
}
/*
测试数据 (六个节点,11条边,ex:0 1 50 节点0 ->  节点1 的distant = 50)
6 11
0 1 50
0 2 10
0 4 70
1 2 15
1 4 10
2 0 20
2 3 15
3 1 20 
3 4 35
4 3 30
5 3 3

*/

[代码运行效果截图]


单源最短路径 (迪杰斯特拉算法)


网友评论    (发表评论)


发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。


扫码下载

加载中,请稍后...

输入口令后可复制整站源码

加载中,请稍后...