Dijkstra算法

  1 #include <iostream>
  2 using namespace std;
  3 #define MAX_VERTEX_NUM 10
  4 #define INF 65535
  5 
  6 //邻接表
  7 struct ENode//边结点
  8 {
  9     int index;//边所指向的点的序号
 10     int info;//记录权值
 11     struct ENode* next;//指向下一条边
 12 };
 13 struct VNode//顶点结点
 14 {
 15     char data;//顶点名称
 16     ENode* first;//指向顶点的第一个邻边
 17 };
 18 struct AGraph//记录图的信息
 19 {
 20     int vexnum, arcnum;//顶点数和边数
 21     VNode p[MAX_VERTEX_NUM];//顶点数组
 22 };
 23 int LocateVex(AGraph *G, char ch)
 24 {
 25     for (int i = 0; i < G->vexnum; i++)
 26         if (ch == G->p[i].data)
 27         {
 28             return i;
 29             break;
 30         }
 31     return -1;
 32 }
 33 //创建邻接表
 34 void CreateAGraph(AGraph *G)
 35 {
 36     int i, j, info;
 37     char v1, v2;
 38     cout << "请输入顶点个数：" << endl; cin >> G->vexnum;
 39     cout << "请输入边的个数：" << endl; cin >> G->arcnum;
 40     cout << "构造顶点：" << endl;
 41     for (int i = 0; i < G->vexnum; i++)//构造顶点数组
 42     {
 43         cin >> G->p[i].data;
 44         G->p[i].first = NULL;
 45     }
 46     cout << "构造邻接表：" << endl;
 47     for (int k = 0; k < G->arcnum; k++)
 48     {
 49         cin >> v1 >> v2 >> info;
 50         i = LocateVex(G, v1);
 51         j = LocateVex(G, v2);
 52         ENode *E = (ENode*)malloc(sizeof(ENode));
 53         E->index = j;
 54         E->info = info;
 55         E->next = G->p[i].first;//头插法
 56         G->p[i].first = E;
 57     }
 58 }
 59 
 60 //
 61 struct TableEntry
 62 {
 63     int known;//标记是否处理过
 64     int dist;//距离
 65     char path;//上一个点，用于记录最短路径
 66 };
 67 typedef struct TableEntry Table[MAX_VERTEX_NUM];
 68 //初始化数组Table
 69 void InitTable(AGraph *G, Table T, int start)//start为开始的那个顶点的编号,T为数组
 70 {
 71     char X=‘X‘;
 72     for (int i = 0; i < G->vexnum; i++)
 73     {
 74         T[i].known = 0;//0表示未处理过
 75         T[i].dist = INF;//距离皆为无穷
 76         T[i].path = X;//表示皆无路径，即没有前面的顶点
 77     }
 78     T[start].dist = 0;
 79 }
 80 //打印路径
 81 void PrintPath(AGraph* G,Table T, char ch,int start)//ch为要到达的顶点，即路径的最后一个顶点
 82 {
 83     int v=LocateVex(G, ch);//获取该点的序号
 84     char Record[MAX_VERTEX_NUM] = {‘/0‘};
 85     int i = 0;
 86     while (T[v].path != G->p[start].data)
 87     {
 88         Record[i] = G->p[v].data;
 89         i++;
 90         v = LocateVex(G, T[v].path);
 91     }
 92     Record[i++] = G->p[v].data;
 93     Record[i] = G->p[start].data;
 94     for (int j = i; j > 0; j--)
 95     {
 96         cout << Record[j] << "->";
 97     }
 98     cout << Record[0] << endl;
 99 }
100 //找出最小距离且未处理过的点
101 int VexSmallestDis(AGraph* G,Table T)
102 {
103     int smallest=-1;
104     for (int i = 0; i < G->vexnum; i++)
105         if (T[i].known == 0)//存在未处理的点
106         {
107             smallest = i;
108             break;
109         }
110     if (smallest != -1)
111     {
112         for (int i = smallest; i < G->vexnum; i++)
113         {
114             if(T[i].known == 0)
115                 if (T[i].dist < T[smallest].dist)
116                     smallest = i;
117         }
118     }
119     return smallest;
120 }
121 //Dijkstra
122 void Dijkstra(AGraph* G,Table T)
123 {
124     while (1)
125     {
126         int v = VexSmallestDis(G, T);//v为目前未处理过的点中dist最小的点
127         if (v == -1)//所有点都已经处理过
128             break;
129         T[v].known = 1;//标为已处理
130         if (G->p[v].first != NULL)//顶点v存在邻近点
131         {//对v的临近点的dist和path进行调整,邻近点的编号为e->index
132             ENode* e = G->p[v].first;
133             while (e != NULL)
134             {
135                 if (T[e->index].known == 0)//v的邻近点尚未处理过
136                     if (T[v].dist + e->info < T[e->index].dist)//如果距离变小则进行调整，否则不用
137                     {
138                         T[e->index].dist = T[v].dist + e->info;
139                         T[e->index].path = G->p[v].data;
140                     }
141                 e = e->next;//处理下一个邻接点
142             }
143         }
144     }
145 }
146 int main()
147 {
148     Table T; char F=‘F‘;
149     AGraph* G = (AGraph*)malloc(sizeof(AGraph));
150     CreateAGraph(G);//创建一个图，邻接表的形式
151     InitTable(G, T, 0);//从顶点0出发到其他顶点（顶点编号从0开始）
152     Dijkstra(G, T);
153     cout << "执行Dijkstra后的T数组：" << endl;
154     for (int i = 0; i < G->vexnum; i++)
155     {
156         cout << T[i].known << " " << T[i].dist << " " << T[i].path;
157         cout << endl;
158     }
159     cout << "路径：" << endl;
160     PrintPath(G, T, F, 0);//从顶点0到F的路径
161     system("pause");
162     return 0;
163 }