-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDijkstra.h
More file actions
88 lines (78 loc) · 1.43 KB
/
Dijkstra.h
File metadata and controls
88 lines (78 loc) · 1.43 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#pragma once
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
/*
Dijkstra
算法设计思想：
1. 初始S={1}
2. 对于i属于V-S 计算1到i的相对S的最短路，长度dist[i]
3. 选择V-S中dist值最小的j,将j加入S，修改V-S中顶点的dist值
4，继续上述过程，直到S=V为止
伪代码：
1. S <- {s}
2. dist <- 0
3. for i属于 V-{s} do
4. dist[i] <- w(s,j)
5. while V-S 不为空 do
从V-S取相对s的最短路径顶点j
S <- S 并 {j}
for i属于V-S do
if dist[j] +w(j,i) < dist[i]
then
dist[i]= dist[j] +w(j,i)
*/
class CDijkstra
{
public:
CDijkstra();
~CDijkstra();
public:
int Dijkstra();
void SetTarget(int nTarget) { m_nTarget = nTarget; }
private:
std::vector<std::vector<int>> m_nWeight;
std::vector<int> m_nvis;
std::vector<int> m_dis;
int m_nNode;
int m_nTarget;
};
CDijkstra::CDijkstra()
{
}
CDijkstra::~CDijkstra()
{
}
int CDijkstra::Dijkstra()
{
//初始化m_nvis[0] 到m_nvis[i] 距离
for (int i = 1; i <= m_nNode; ++i)
{
m_dis[i] = m_nWeight[0][i];
}
m_nvis[0] = 1; //标记起始点
for (int i = 1; i <= m_nNode; ++i)
{
int nMin = INT_MAX;
int k = 0;
for (int j= 1;j <= m_nNode;++j)
{
if (!m_nvis[j] && m_dis[j] < nMin)
{
nMin = m_dis[j];
k = j;
}
}
m_nvis[k] = 1; // 标记找到的最近点
//判断v[0]到v[j]短还是经过v[k]短
for (int j = 1; j <= m_nNode; ++j)
{
if (!m_nvis[j] && nMin+ m_nWeight[k][j] < m_dis[j])
{
m_dis[j] = nMin + m_nWeight[k][j];
}
}
}
return m_dis[m_nTarget];
}