经验C++课本Dijkstra算法Cpp实现及改正
JJuprising01点17分，又是一个与奇怪问题较量的夜晚，这一次，我又成功解决了。
起因是发现数据结构书上关于Dijkstra算法的实现有点错误，想要自己更正一下，通过在不同位置插入输出字符来调试代码，找到了几处错漏。
96行的char直接赋值给string出现乱码，两种办法，一是string+=char，另一种是string.puch_back(char)
107行，由于是无向图，有可能路径会重复连上两次，我们要让路径不再逆向连接，例如A起始，默认第一轮是已知AB最短为10，在判断最短路径时，没有排除A，到时AB又连上A，变成ABA，而这个ABA是在path[0]上的，虽然每轮输出最短路径时就不需要输出path[起始点]，这样子的错误也是无妨，只需要跳过path[起始点]即可，但是在调试过程中发现这个错漏，还是从根本上修正，可以把它改成有向图，把初始化的arc[j][i]=w去掉。
(自己的问题)输出结果为?，发现原来是经典for循环是其他变量在递增时还是写了i++…导致循环出不来
还有一个注意点需要补充，就是可变参数友元函数的声明:
1
2
3
4
5
6
7
8
9
10
11
12
13
| template <class DataType>
class MGraph
{
...
template <class T>
friend void Dijkstra(MGraph<T> MG,int v);
}
template <class DataType>
void Dijkstra(MGraph<DataType> MG,int v){
...
}
|
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
#include <iostream>
using namespace std;
#include<string>
const int MaxSize = 10;
int visited[MaxSize]={0};
struct element
{
int lowcost, adjvex;
};
int Min(int dist[],int ver){
int min=255,minNum=0;
for(int i=0;i<ver;i++){
if(dist[i]<min&&dist[i]>0){
min=dist[i];
minNum=i;
}
}
return minNum;
}
template <class DataType>
class MGraph
{
public:
MGraph(DataType a[ ], int n, int e);
~MGraph( ) { }
void DFSTraverse(int v);
void BFSTraverse(int v);
template <class T>
friend void Dijkstra(MGraph<T> MG,int v);
private:
DataType vertex[MaxSize];
int arc[MaxSize][MaxSize];
int vertexNum, arcNum;
};
template <class DataType>
MGraph<DataType>::MGraph(DataType a[ ], int n, int e)
{
int i, j, w=0;
vertexNum=n; arcNum=e;
for (i=0; i<vertexNum; i++)
vertex[i]=a[i];
for (i=0; i<vertexNum; i++)
for (j=0; j<vertexNum; j++)
arc[i][j]=255;
for (int k=0; k<arcNum; k++)
{
cout<<"请输入边的两个顶点的序号：";
cin>>i;
cin>>j;
cout<<"请输入边的权值：";
cin>>w;
arc[i][j]=w;
}
}
template <class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{
cout << vertex[v]; visited[v] = 1;
for (int j = 0; j < vertexNum; j++)
if (arc[v][j] <255 && visited[j]==0)
DFSTraverse(j);
}
template <class DataType>
void MGraph<DataType>::BFSTraverse(int v)
{
int Q[MaxSize];
int front = -1, rear = -1;
cout << vertex[v]; visited[v] = 1; Q[++rear] = v;
while (front != rear)
{
v = Q[++front];
for (int j = 0; j < vertexNum; j++)
if (arc[v][j] <255 && visited[j] == 0 ) {
cout << vertex[j];
visited[j] = 1;
Q[++rear] = j;
}
}
}
template <class DataType>
void Dijkstra(MGraph<DataType> MG,int v){
int i,k,num,dist[MaxSize];
string path[MaxSize];
for(int i=0;i<MG.vertexNum;i++){
dist[i]=MG.arc[v][i];
if(dist[i]!=255){
path[i].push_back(MG.vertex[v]);
path[i].push_back(MG.vertex[i]);
}
else path[i]="";
cout<<"|"<<i<<" "<<path[i]<<"|"<<" ";
}
cout<<endl;
for(num=1;num<MG.vertexNum;num++){
k=Min(dist,MG.vertexNum);
cout<<"path"<<k<<" "<<path[k]<<","<<dist[k]<<";";
for(i=0;i<MG.vertexNum;i++){
if(dist[i]>dist[k]+MG.arc[k][i]){
dist[i]=dist[k]+MG.arc[k][i];
path[i]=path[k]+MG.vertex[i];
}
}
dist[k]=0;
cout<<endl;
}
}
int main()
{
char ch[]={'A','B','C','D','E'};
MGraph<char> MG(ch, 5, 7);
for (int i=0; i<MaxSize; i++)
visited[i]=0;
cout<<"深度优先遍历序列是：";
MG.DFSTraverse(0);
cout<<endl;
for (int i=0; i<MaxSize; i++)
visited[i]=0;
cout<<"广度优先遍历序列是：";
MG.BFSTraverse(0);
cout<<endl;
cout<<"从顶点"<<ch[0]<<"到各终点的最短路径分别是："<<endl;
Dijkstra(MG,0);
cout<<endl;
system("pause");
return 0;
}
|
