我一开始写成了最小生成树的代码,最小生成树一直在选最小的那条边,对每个节点来说,它到原点的距离不一定是最近的。
#include
using namespace std;
#include
#include
class Node
{
public:
Node(int name):_name(name){}
void set_father(int father) {
_father = father;
}
int get_father()
{
return _father;
}
private:
int _name;
int _father = -1;
};
int main()
{
const int numNode = 7;
int weights[numNode + 1][numNode+1];
for (int i = 0; i < numNode + 1; ++i)
{
for (int j = 0; j < numNode + 1; ++j)
{
if (i == j) weights[i][j] = 0;
else weights[i][j] = INT_MAX / 2 - 1;
}
}
weights[1][2] = 12;
weights[2][1] = 12;
weights[2][3] = 10;
weights[3][2] = 10;
weights[3][4] = 3;
weights[4][3] = 3;
weights[4][5] = 4;
weights[5][4] = 4;
weights[5][6] = 2;
weights[6][5] = 2;
weights[6][7] = 9;
weights[7][6] = 9;
weights[1][7] = 14;
weights[7][1] = 14;
weights[1][6] = 16;
weights[6][1] = 16;
weights[6][2] = 7;
weights[2][6] = 7;
weights[3][5] = 5;
weights[5][3] = 5;
weights[5][7] = 8;
weights[7][5] = 8;
Node one(1);
Node two(2);
Node three(3);
Node four(4);
Node five(5);
Node six(6);
Node seven(7);
list<int> visited_nodes;
// 求各点到点4的最短距离,并输出最短路径
int distanceTo4[numNode + 1];
bool visited[numNode + 1];
for (int i = 0; i < numNode + 1; ++i) // 最短距离初始化
{
distanceTo4[i] = INT_MAX / 2 - 1;
}
distanceTo4[4] = 0;
for (int i = 0; i < numNode + 1; ++i) // 是否已经访问初始化
{
visited[i] = false;
}
visited[4] = true;
int updateIndex = 4;
visited_nodes.push_back(updateIndex);
while (visited_nodes.empty() == false)
{
int preUpdateIndex = visited_nodes.front();
visited_nodes.pop_front();
for (int i = 1; i < numNode + 1; ++i)
{
if (weights[i][preUpdateIndex] < 1000)
{
// 说明是preUpdateIndex的邻居
int tmpDistance = min(
distanceTo4[i],
distanceTo4[preUpdateIndex] + weights[i][preUpdateIndex]);
if (tmpDistance == (distanceTo4[preUpdateIndex] + weights[i][preUpdateIndex]) && distanceTo4[i]!=tmpDistance)
{
// 说明更新了
switch (i)
{
case 1:
{
one.set_father(preUpdateIndex);
}break;
case 2:
{
two.set_father(preUpdateIndex);
}break;
case 3:
{
three.set_father(preUpdateIndex);
}break;
case 4:
{
four.set_father(preUpdateIndex);
}break;
case 5:
{
five.set_father(preUpdateIndex);
}break;
case 6:
{
six.set_father(preUpdateIndex);
}break;
case 7:
{
seven.set_father(preUpdateIndex);
}break;
default: break;
}
visited_nodes.push_back(i);
}
distanceTo4[i] = tmpDistance;
}
}
}
for (int i = 1; i < numNode + 1; ++i)
{
cout << distanceTo4[i] << " ";
}
cout << endl;
// 打印从1->4的最短路径
vector<int> path14;
path14.push_back(1);
Node *node;
node = &one;
while (true)
{
int index = node->get_father();
if (index == -1) break;
path14.push_back(index);
switch (index)
{
case 1:
node = &one; break;
case 2:
node = &two; break;
case 3:
node = &three; break;
case 4:
node = &four; break;
case 5:
node = &five; break;
case 6:
node = &six; break;
case 7:
node = &seven; break;
default: break;
}
}
for (int i = 0; i < path14.size(); ++i)
{
if (i != 0) {
cout << "->" << path14[i];
}
else {
cout << path14[i];
}
}
cout << endl;
return 0;
}