Dijkstra最短路径——2017华为实习在线机试
题目大致就是找到一个图的最短路径，没什么新意，不过关键是！关键是！我没写出来……上上篇文章——图的所有路径输出可以解决，不过要计算所有路径，工作量比较大，可能是超时。
对于这种无负边的最短路径可以用Dijkstra求解。
代码注释很全，可以直接看懂：
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <list>
#include <stack>
#include <queue>
using namespace std;
typedef struct point{
int x;
int y;
point *previous;
int step;
} point;
/*
int map = {
{ 0, 2, 10, 5, 3, -1 },
{ -1, 0, 12, -1, -1, 10 },
{ -1, -1, 0, -1, 7, -1 },
{ 2, -1, -1, 0, 2, -1 },
{ 4, -1, -1, 1, 0, -1 },
{ 3, -1, 1, -1, 2, 0 }
};*/
int map = {
{ -1, 2, 10, -1, 3, -1 },
{ -1, -1, 12, -1, -1, 10 },
{ -1, -1, -1, -1, 7, -1 },
{ -1, -1, -1, -1, -1, -1 },
{ 4, -1, -1, -1, -1, -1 },
{ 3, -1, 1, -1, 2, -1 }
};
/*
int map = {
{-1,-1,10,-1,30,100},
{-1,-1,5,-1,-1,-1},
{-1,-1,-1,50,-1,-1},
{-1,-1,-1,-1,-1,10},
{-1,-1,-1,20,-1,60},
{-1,-1,-1,-1,-1,-1},
};*/
/*
int map = {
{ -1, -1, 10, -1, 30, 100 },
{ -1, -1, 5, -1, -1, -1 },
{ -1, -1, -1, 50, -1, -1 },
{ -1, -1, -1, -1, -1, 10 },
{ -1, -1, -1, 20, -1, 60 },
{ -1, -1, -1, -1, -1, -1 },
};*/
void PrintMostShortPath(vector<int> path, vector<int> D, int startPoint, int endPoint)
{
int s = endPoint;
vector<int> v;
v.push_back(endPoint);
while (path != startPoint)
{
v.push_back(path);
s = path;
}
v.push_back(startPoint);
cout << "最短路径为：";
for (int i = v.size() - 1; i >= 0; i--)
{
cout << " " << v;
}
cout << endl;
cout << "最距离为为：" << D << endl;
}
void PrintIntVector(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v << "\t";
}
cout << endl;
}
void PrintBoolVector(vector<bool> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v << "\t";
}
cout << endl;
}
//算法对于负边图无效
void Dijkstra(int startPoint,int endPoint)
{
//获取图边长
int n = 6;
//初始化变量
vector<bool> S(n);//标记节点是否走过
vector<int> D(n);//从起点到该点的最短距离
vector<int> Path(n);//该点的前驱节点
int v = 0;
int min = 0;
//初始化变量
for (int i = 0; i < n; i++)
{
S = false;
D = map;
//有边
if (D >0)
{
Path = startPoint;
}
else
{
Path = -1;
}
}
S = true;
D = 0;
//初始化打印
cout << "已经走过的节点S: "; PrintBoolVector(S);
cout << "当前最短路径D: "; PrintIntVector(D);
cout << "前驱符号Path： "; PrintIntVector(Path);
//再循环n-1次，把剩下的n-1个节点都走一遍
for (int j = 1; j < n; j++)
{
min = 32767;
v = 0;
//寻找当前最短路径D中，未走过并且，可以到达的，距离最短节点。
for (int i = 0; i < n; i++)
{
if (S == false && D != -1 && (D < min))
{
v = i;
min = D;
}
}
S = true;//v为中转节点，标记走过
//以v为中转点走到i节点和现有到i路径比较
for (int i = 0; i < n; i++)
{
//这个||很关键。两种需要更新的情况。一种是通过中转小于目前的最短距离，另一种是直接可以到的（在map中有v到i的路径）
//第一个：没走过的点，第二个：能走的点，第三个：1.通过中转点走比直接走小2.在map中v-i可以走，但是在D中未更新的情况
//dijkstra关键有就是一个更新的操作
if (S == false && map != -1 && (D + map < D || D == -1))
{
D = D + map;
Path = v;
}
}
//打印每次的结果
cout << "第" << j << "次：" << endl;
cout << "已经走过的节点S: "; PrintBoolVector(S);
cout << "当前最短路径D: "; PrintIntVector(D);
cout << "前驱符号Path： "; PrintIntVector(Path);
}
PrintMostShortPath(Path, D, startPoint, endPoint);
}
int main()
{
int startPoint = 4;
int endPoint = 1;
Dijkstra(startPoint, endPoint);
return 0;
}
View Code 结果如下
页:
[1]