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

[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

*/

[代码运行效果截图]