图的最短路径——DIJ算法，有向图的矩阵实现，图的基本操作
图是一种非常重要的数据结构，在研究从一点出发到各个顶点的最短距离。
实验目的
1. 掌握图的基本概念、表示方法、遍历方法。
实验要求
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 << "请输入第"<> i >> j >> w;if(i 遍历
深度遍历——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 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
#include
#includeusing 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 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 << "请输入第"<> i >> j >> w;if(i> 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;
} 
