会python真的可以为所欲为0(回)
339天前
这里还有人吗1(回)
525天前这里还有人吗0(回)
525天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
749天前到处都是羊，不想上班0(回)
829天前
鸽子
0(回)
833天前// 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 |
*/ |
