手撕算法系列----Dijkstra单源最短路径
前言
纯小白手撕一波dijkstra,十分简陋,有问题望指出。
理论
暂无理论哈哈哈哈(ps:懒得写,主要图好难画,下次一定补上!)
给个链接你们看链接
代码
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
#define GRAPH_INFINITY 65535 /* 无穷大 */
#define MAXVEX 5 /*最大图顶点*/
#define MAXEDGE 20 /*最大图边*/
vector<vector<int>> createGraph()
{
vector<vector<int>> graph(MAXVEX,vector<int>(MAXVEX,0));
int n = graph.size();
int m = graph[0].size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i+1; j++)
{
graph[i][j] = rand()%10;
if (graph[i][j] == 0) graph[i][j] = 1;
graph[j][i] = graph[i][j];
}
}
return graph;
}
int main()
{
vector<vector<int>> graph = createGraph();
int n = graph.size();
int m = graph[0].size();
graph[0][0] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cout << graph[i][j] << " ";
}
cout << endl;
}
vector<int> vertex(n,0);
vector<int> distance(n);
queue<int> q;
for (int i = 0; i < n; i++)
{
distance[i] = GRAPH_INFINITY;
}
vertex[0] = 1;
distance[0] = 0;
q.push(0);
while (!q.empty())
{
int q_top = q.front();
q.pop();
int min_val = GRAPH_INFINITY + 1;
for (int i = 0; i < n; i++)
{
if (graph[q_top][i] != -1 && vertex[i] != 1)
{
distance[i] = min(distance[i], graph[q_top][i] + distance[q_top]);
min_val = min(min_val, distance[i]);
}
}
for (int j = 0; j < n; j++)
{
if (min_val == distance[j] && vertex[j] != 1)
{
vertex[j] = 1;
q.push(j);
cout << "本轮选取" << j << endl;
break;
}
}
cout << "distance:" << " ";
for (int i = 0; i < n; i++)
{
cout << distance[i] << " ";
}
cout << endl;
}
//// for (int i = 0; i < n; i++)
// {
// cout << distance[i] << " ";
// }
return 0;
}