- const int MAXNUM = 10;
- int dist[MAXNUM]; //dist[i] 表示当前情况下从v0到结点i的路径值
- int pre[MAXNUM];
- int A[MAXNUM][MAXNUM]; //初始时为结点i到结点j的路径值
- void Dijkstra(int v0,int n)
- {
- bool s[MAXNUM]; //标记结点i是否加入集合S中
- for (int i = 1;i <= n;i++)
- {
- dist[i] = A[v0][i]; //初始dist的值
- s[i] = false;
- if (dist[i] == INT_MAX)
- {
- pre[i] = -1;
- }
- else
- pre[i] = v0;
- }
- s[v0] = 0;
- s[v0] = true;
- for (int i = 2;i <= n;i++) //除了最后一个结点和v0不用考虑,其他结点都得考虑,总共n-2次
- {
- int iMax = INT_MAX;
- int iCur = v0;
- for (int j = 1;j <= n;j++)
- {
- if ((!s[j]) && iMax > dist[j])
- {
- iMax = dist[j];
- iCur = j;
- }
- }
- s[iCur] = true;
- for (j = 1;j <= n;j++)
- {
- if (!s[j])
- {
- if (dist[iCur] + A[iCur][j] < A[v0][j])
- {
- dist[j] = dist[iCur] + A[iCur][j];
- pre[j] = iCur;
- }
- }
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/0402201511732.html
来源: http://www.codesnippet.cn/detail/0402201511732.html