8000 add dijkstra algorithm demo · mikephp/basic_data_struct@7b21dc1 · GitHub
[go: up one dir, main page]
Skip to content

Commit 7b21dc1

Browse files
mikephpmikephp
committed
add dijkstra algorithm demo
1 parent 232c9eb commit 7b21dc1

File tree

1 file changed

+117
-0
lines changed

1 file changed

+117
-0
lines changed

‎src/dijkstra.cpp

Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
// dihkstra.cpp : 定义控制台应用程序的入口点。
2+
// building envirenment vs 2010
3+
//
4+
5+
#include "stdafx.h"
6+
7+
/*int _tmain(int argc, _TCHAR* argv[])
8+
{
9+
return 0;
10+
}*/
11+
#include <iostream>
12+
13+
using namespace std;
14+
15+
#define MAX 9999999
16+
17+
#define LEN 210
18+
19+
int map[LEN][LEN]; //某点到某点两点间的的距离
20+
int dist[LEN]; //记录当前点到源点的最短路径长度
21+
int mark[LEN]; //加入进来的点的集合
22+
23+
24+
25+
//初始化map为正无穷大
26+
void init()
27+
{
28+
int i,j;
29+
for(i=0;i<LEN;i++)
30+
{
31+
for(j=0;j<LEN;j++)
32+
{
33+
map[i][j]=MAX;
34+
}
35+
}
36+
}
37+
38+
//n:多少条路 start:起始点
39+
//dist[i],最后存储着start 到i点的最短距离
40+
void myDijstra(int n,int start)
41+
{
42+
int i,j,min,pos;
43+
for(i=1;i<=n;i++)
44+
{
45+
mark[i]=0;//没有点加入
46+
dist[i]=map[start][i];//把start 附近点 dis[]初始化
47+
}
48+
49+
mark[start]=1;//把起始点加进来
50+
dist[start]=0;
51+
52+
for(i=1;i<=n;i++)
53+
{
54+
55+
min=MAX;
56+
for(j=1;j<=n;j++)
57+
{
58+
if(!mark[j] && dist[j]<min)
59+
{ //取出不在mark里的最小的dist[i]
60+
min=dist[j];
61+
pos=j;//标记
62+
}
63+
64+
}
65+
66+
if(min==MAX)//已经不能通了
67+
break;
68+
69+
mark[pos]=1;//把K加进来
70+
71+
//做松弛操作
72+
for(j=1;j<=n;j++)
73+
{
74+
if(!mark[j] && dist[j]>dist[pos]+map[pos][j])//start->j or start->pos,pos->j
75+
{
76+
dist[j]=dist[pos]+map[pos][j];//这步跟prim算法有点不同
77+
}
78+
}
79+
}
80+
}
81+
82+
int main()
83+
{
84+
int i,n,line;
85+
int a,b,d;
86+
scanf("%d%d",&n,&line);//输入点和
87+
init();
88+
for(i=0;i<line;i++)
89+
{
90+
91+
scanf("%d%d%d",&a,&b,&d); //输入各边的权值
92+
// 这个判断是防止重边的，因为也许会对同一条路给出两个值，这时就保存较小的值
93+
if(map[a][b]>d)
94+
{
95+
map[a][b]=map[b][a]=d;
96+
}
97+
}
98+
99+
myDijstra(n,1);//调用方法(点数，起始点)
100+
101+
//输出1到5的最短路径
102+
cout<<dist[5]<<endl;
103+
104+
return 0;
105+
}
106+
107+
/*
108+
5 7
109+
1 2 10
110+
1 4 30
111+
1 5 100
112+
2 3 50
113+
3 5 10
114+
4 3 20
115+
4 5 60
116+
60
117+
*/

0 commit comments

Comments
 (0)
0