图的最短路径——DIJ算法，有向图的矩阵实现，图的基本操作

article/2025/8/30 9:28:02

图是一种非常重要的数据结构，在研究从一点出发到各个顶点的最短距离。

实验目的

1. 掌握图的基本概念、表示方法、遍历方法。

2. 掌握图的最短路径算法。

实验要求

1．输入图的顶点数n（不超过10个）、边数m，顶点分别用0到n-1表示；

2．采用“起始顶点，终止顶点，权值”输入图的m条边，创建图；

3．输出从顶点0开始的BFS遍历、DFS遍历的顶点遍历顺序；

4．输出从顶点0到其余顶点最短路径及最短路径的长度，如果没有路经，输出0。

程序实现

主程序

int main() {int n, m,point1,point2,weight;cout << "\n请输入顶点n数,边数m值\n";cin >> n >> m;cout << "请输入起始顶点，终止顶点，权值，顶点范围  [0 n-1]\n";cout << "形如 0 4 6\n";CreatMap(n, m);cout << "\n广度遍历 BFS\n";BFS(map);cout << "\n深度遍历 DFS\n";DFS(map);ShortestPath_DIJ(map, 0);cout << "\nMap";return 0;
}

1 ，2 输入图的顶点数n（不超过10个）、边数m，顶点分别用0到n-1表示；

创建有向图

//creat map
#define INFINITY 100000
#define MAX_VERTEX_NUM 10 //最大顶点数typedef struct {int vexs[MAX_VERTEX_NUM];int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum, arcnum;
}MGraph;MGraph map;//创建图
void CreatMap(int n, int m) {map.vexnum = n;map.arcnum = m;int i, j, w;for (i = 0; i < n; i++)map.vexs[i] = i ;for (i = 0; i < n; i++)for (j = 0; j < n; j++)map.arcs[i][j] = INFINITY;for (int k = 1; k <= m; k++) {//想依次输入可添加下面一行；//cout << "请输入第"<<k<<"条边起始顶点，终止顶点，权值\n";cin >> i >> j >> w;if(i<n&&j<n)                   //防止i，j溢出；map.arcs[i][j] = w;else {cout << "输入顶点不存在\n";k--;}}cout << "打印邻接矩阵,0表示不邻接\n\n";for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {if (map.arcs[i][j] == INFINITY)cout << "0  ";elsecout << map.arcs[i][j]<<"   ";}cout << '\n';}
}

遍历

深度遍历——DFS

int DFSvisited[10];
void DFS(MGraph m,int v) {cout << m.vexs[v]<<"  ";DFSvisited[v] = -1;int w;for (w = 0; w < m.vexnum; w++) {if (DFSvisited[w] != -1&&m.arcs[v][w] != INFINITY)DFS(m, w);}
}
void DFS(MGraph m) {for (int i=0; i < 10; i++)DFSvisited[i] = i;for (int i = 0; i < m.vexnum; i++)if(DFSvisited[i] != -1)DFS(m, i);
}

BFS

void BFS(MGraph m) {int visited[10];for (int i = 0; i < 10; i++) {visited[i] = 1;}queue<int> Q;for (int v = 0; v < m.vexnum; v++) {if (visited[v] == 1) {visited[v] = -1;cout << m.vexs[v]<<"  ";Q.push(v);while (!Q.empty()) {int u;u = Q.front();Q.pop();for (int w = 0; w < m.vexnum; w++) {if (visited[w] == 1&&m.arcs[u][w]!=INFINITY) {cout << m.vexs[w] << "  ";visited[w] = -1;Q.push(w);}}}}}}

从一点出发最短路径

void ShortestPath_DIJ(MGraph G, int V0) {int P[10][10], D[10],final[10], v, w;int path[10][10];for ( v = 0; v < G.vexnum; v++) {final[v] = 0;D[v] = G.arcs[V0][v];for ( w = 0; w < G.vexnum; w++) {P[v][w ] = 0;path[v][w] = -1;}if (D[v] < INFINITY) {P[v][V0] = 1;P[v][v] = 1;path[v][0] = 0;path[v][1] = v;}}D[V0] = 0;final[V0] = 1;for (int i = 1; i < G.vexnum; i++) {int min = INFINITY;int minpath[10];for ( w = 0; w < G.vexnum; w++) {if(final[w]==0)if (D[w] < min) {v = w;min = D[w];for (int k = 0; k < 10; k++)minpath[k] = path[v][k];}}final[v] = 1;for (w = 0; w < G.vexnum; w++) {if ((final[w] == 0) && ((min + G.arcs[v][w]) < D[w])) {D[w] = min + G.arcs[v][w];int k;for (k = 0; minpath[k] != -1; k++)path[w][k] = path[v][k];path[w][k] = w;for (int i = 0; i < G.vexnum; i++) {P[w][i] = P[v][i];}P[w][w] = 1;}}}

测试：

总程序：

#include<iostream>
#include<cstdlib>
#include<queue>using namespace std;/*
1． 输入图的顶点数n（不超过10个）、边数m，顶点分别用0到n-1表示；
2． 采用“起始顶点，终止顶点，权值”输入图的m条边，创建图；
3． 输出从顶点0开始的BFS遍历、DFS遍历的顶点遍历顺序；
4． 输出从顶点0到其余顶点最短路径及最短路径的长度，如果没有路经，输出0。
*///creat map
#define INFINITY 100000
#define MAX_VERTEX_NUM 10 //最大顶点数typedef struct {int vexs[MAX_VERTEX_NUM];int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum, arcnum;
}MGraph;MGraph map;void BFS(MGraph m) {int visited[10];for (int i = 0; i < 10; i++) {visited[i] = 1;}queue<int> Q;for (int v = 0; v < m.vexnum; v++) {if (visited[v] == 1) {visited[v] = -1;cout << m.vexs[v]<<"  ";Q.push(v);while (!Q.empty()) {int u;u = Q.front();Q.pop();for (int w = 0; w < m.vexnum; w++) {if (visited[w] == 1&&m.arcs[u][w]!=INFINITY) {cout << m.vexs[w] << "  ";visited[w] = -1;Q.push(w);}}}}}}int DFSvisited[10];
void DFS(MGraph m,int v) {cout << m.vexs[v]<<"  ";DFSvisited[v] = -1;int w;for (w = 0; w < m.vexnum; w++) {if (DFSvisited[w] != -1&&m.arcs[v][w] != INFINITY)DFS(m, w);}
}
void DFS(MGraph m) {for (int i=0; i < 10; i++)DFSvisited[i] = i;for (int i = 0; i < m.vexnum; i++)if(DFSvisited[i] != -1)DFS(m, i);
}//创建图
void CreatMap(int n, int m) {map.vexnum = n;map.arcnum = m;int i, j, w;for (i = 0; i < n; i++)map.vexs[i] = i ;for (i = 0; i < n; i++)for (j = 0; j < n; j++)map.arcs[i][j] = INFINITY;for (int k = 1; k <= m; k++) {//想依次输入可添加下面一行；//cout << "请输入第"<<k<<"条边起始顶点，终止顶点，权值\n";cin >> i >> j >> w;if(i<n&&j<n)                   //防止i，j溢出；map.arcs[i][j] = w;else {cout << "输入顶点不存在\n";k--;}}cout << "打印邻接矩阵,0表示不邻接\n\n";for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {if (map.arcs[i][j] == INFINITY)cout << "0  ";elsecout << map.arcs[i][j]<<"   ";}cout << '\n';}
}void ShortestPath_DIJ(MGraph G, int V0) {int P[10][10], D[10],final[10], v, w;int path[10][10];for ( v = 0; v < G.vexnum; v++) {final[v] = 0;D[v] = G.arcs[V0][v];for ( w = 0; w < G.vexnum; w++) {P[v][w ] = 0;path[v][w] = -1;}if (D[v] < INFINITY) {P[v][V0] = 1;P[v][v] = 1;path[v][0] = 0;path[v][1] = v;}}D[V0] = 0;final[V0] = 1;for (int i = 1; i < G.vexnum; i++) {int min = INFINITY;int minpath[10];for ( w = 0; w < G.vexnum; w++) {if(final[w]==0)if (D[w] < min) {v = w;min = D[w];for (int k = 0; k < 10; k++)minpath[k] = path[v][k];}}final[v] = 1;for (w = 0; w < G.vexnum; w++) {if ((final[w] == 0) && ((min + G.arcs[v][w]) < D[w])) {D[w] = min + G.arcs[v][w];int k;for (k = 0; minpath[k] != -1; k++)path[w][k] = path[v][k];path[w][k] = w;for (int i = 0; i < G.vexnum; i++) {P[w][i] = P[v][i];}P[w][w] = 1;}}}cout << "\n输出最短路径P\n";for (int i = 0; i < G.vexnum; i++) {cout << "\n第" << i << "个顶点：" << "长度：" ;if (D[i] != INFINITY) {cout << D[i] << "  路径：";for (int j = 0; path[i][j] != -1; j++) {cout << path[i][j] << "  ";}}elsecout << 0 << "  不可达";cout << endl;;}for (int j = 0; j < G.vexnum; j++) {if(D[j]!=INFINITY)cout << D[j] << "  ";elsecout << 0 << "  ";}}
int main() {int n, m,point1,point2,weight;cout << "\n请输入顶点n数,边数m值\n";cin >> n >> m;cout << "请输入起始顶点，终止顶点，权值，顶点范围  [0 n-1]\n";cout << "形如 0 4 6\n";CreatMap(n, m);cout << "\n广度遍历 BFS\n";BFS(map);cout << "\n深度遍历 DFS\n";DFS(map);ShortestPath_DIJ(map, 0);cout << "\nMap";return 0;
}