# 最短路径迪杰斯特拉算法

xiaoxiao2021-02-28  2

#include<iostream> using namespace std; #define max 10 #define maxint 320 typedef struct listtu { int edgenum; int vernum; char mvex[max]; int matrix[max][max]; }; listtu inital() { listtu Q; Q.edgenum = 0; Q.vernum = 0; return Q; } int getposition(char ch, listtu Q) { for (int i = 0;i<Q.vernum;i++) { if (Q.mvex[i] == ch) { return i; } } return -1; } void create(listtu &Q, char vexs[], int vlen, char edges[][2], int edgelen, int weight[]) { char c1, c2; Q.edgenum = edgelen; Q.vernum = vlen;int p1, p2; //初始化顶点 for (int i = 0;i<vlen;i++) { Q.mvex[i] = vexs[i]; } //初始化邻接矩阵 for (int i = 0;i < vlen;i++) { for (int j = 0;j < vlen;j++) { Q.matrix[i][j] = max; } } for (int i = 0;i<edgelen;i++) { p1 = getposition(edges[i][0], Q); p2 = getposition(edges[i][1], Q); Q.matrix[p1][p2] = 1; } } void print(listtu Q) { for (int i = 0;i<Q.vernum;i++) { for (int j = 0;j < Q.vernum;j++) { cout << Q.matrix[i][j] << " "; } cout << endl; } } char readchar() { char ch; do { cin >> ch; } while (!((ch >= 'a'&&ch <= 'z') || (ch >= 'A'&&ch <= 'Z'))); return ch; } void create1(listtu &Q) { char c1, c2;int p1, p2;char a;int c3; cout << "输入顶点数"; cin >> Q.vernum; cout << "输入边数"; cin >> Q.edgenum; if (Q.vernum < 1 || Q.edgenum<1 || (Q.edgenum>(Q.vernum*(Q.vernum - 1)))) { cout << "输入错误：不合法的参数" << endl; return; } for (int i = 0;i<Q.vernum;i++) { cout << "vertex(" << i << "):"; Q.mvex[i] = readchar(); } //初始化邻接矩阵 for (int i = 0;i <Q.vernum;i++) { for (int j = 0;j < Q.vernum;j++) { Q.matrix[i][j] = maxint; } } for (int i = 0;i<Q.edgenum;i++) { cout << "edges(" << i << "):"; c1 = readchar(); c2 = readchar(); p1 = getposition(c1, Q); p2 = getposition(c2, Q); cout << "输入权值"; cin >> c3; Q.matrix[p1][p2] = c3; } } void shortest(listtu &Q, char v0) { int path[max][max]; int s[max]; int d[max]; int min; int p = getposition(v0, Q); for (int i = 0;i < Q.vernum;i++) { s[i] = false; d[i] = Q.matrix[p][i]; for (int j = 0;j < Q.vernum;j++) { path[i][j] = -1; } if (d[i] < maxint) { path[i][0] = p; path[i][1] = i; } } s[p] = true; d[p] = 0; for (int i = 1;i < Q.vernum;i++) { min = maxint; for (int j = 0;j < Q.vernum;j++) { if (!s[j] && d[j]<min) { p = j; min = d[j]; } } s[p] = true; for (int j = 0;j < Q.vernum;j++) { if (!s[j] &&(d[p] + Q.matrix[p][j] < d[j])) { d[j] = d[p] + Q.matrix[p][j]; for (int k = 0;k < Q.vernum;k++) { int a = path[p][k]; path[j][k]=a; if (path[j][k] == -1) { path[j][k] = j; break; } } } } } for (int i = 0;i < Q.vernum;i++) { for (int j = 0;j < Q.vernum;j++) { cout << path[i][j] << " "; } cout << endl; } for (int i = 0;i < Q.vernum;i++) { cout << Q.mvex[0] << " " << Q.mvex[i] << " " << d[i]; cout << "最短路径为："; for (int j = 0;j < Q.vernum;j++) { if (path[i][j]>-1) { cout << Q.mvex[path[i][j]] << " "; } } cout << endl; } } int main() { /*char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' }; char edges[][2] = { { 'A', 'C' }, { 'A', 'D' }, { 'A', 'F' }, { 'B', 'C' }, { 'C', 'D' }, { 'E', 'G' }, { 'F', 'G' } }; int weight[] = { 1,2,3,4,5,6,7,8,9 }; int vlen = sizeof(vexs) / sizeof(vexs[0]); int elen = sizeof(edges) / sizeof(edges[0]);*/ listtu Q;Q = inital(); //create(Q, vexs, vlen, edges, elen, weight); create1(Q); print(Q); shortest(Q, 'A'); }