C++ Dijkstra算法 邻接矩阵形式

C++ Dijkstra算法 邻接矩阵形式

图在计算机内处理需要转换成邻接矩阵等矩阵类型
才能方便运算

​#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>#define Inf 0x3f3f3f3f//最大值using namespace std;int map[1005][1005];//图论的邻接矩阵
int vis[1005];//标记,被标记的元素下次不能被使用
int dis[1005];//记录移动
int n, m;//n代表结点	m表示边void init() {//初始化邻接矩阵memset(&map, Inf, sizeof(map));for (int i = 1;i <= 1005;i++)map[i][i] = 0;//没有环
}inline int read() {//快速写入int ff = 1;int ret = 0;char ch = getchar();while (!isdigit(ch)) {if (ch == '-') ff = -ff;ch = getchar();}while (isdigit(ch)) {ret = ret * 10 + ch - '0';ch = getchar();}return ff * ret;
}void scanner() {//把图写入邻接矩阵int u, v, x;for (int i = 1;i <= m;i++) {u = read(), v = read(), x = read();if (map[u][v] > x) {map[u][v] = x;map[v][u] = x;}}
}/*测试数据
9 6
1 2 1
1 3 12
2 3 9
2 4 3
3 4 4
3 5 5
4 5 13
4 6 15
5 6 4right printf-->17
*/void Dijkstra(int n) {memset(vis, 0, sizeof(vis));//可忽略,全局变量已经初始化0for (int i = 1;i <= n;i++)dis[i] = map[n][i];//获得最后一列(行)数据vis[n] = 1;//标记最后一个元素不能被使用for (int t = 1;t < n;t++) {int minn = Inf, temp;for(int i=1;i<=n;i++)if (!vis[i] && dis[i] < minn) {//判断该元素能被使用且属于最小值minn = dis[i];temp = i;}vis[temp] = 1;//标记该当前最小元素不能再被使用for (int i = 1;i <= n;i++)//被标记的元素+矩阵对应列(行)内的某个元素小于对应数据if (map[temp][i] + dis[temp] < dis[i])dis[i] = map[temp][i] + dis[temp];}
}int main() {m = read(), n = read();init();scanner();Dijkstra(n);printf("%d", dis[1]);return 0;
}​