- #define N 7
- /* Unreached */
- #define M 999999
- /*
- a1--100--b1 a3--001--e1 a2--020--d1
- b1--100--a1 b2--050--g1 b3--020--c2
- c1--005--d3 c2--020--b3 c3--040--g2 c4--010--f3
- d1--020--a2 d2--040--f2 d3--005--c1
- e1--001--a3 e2--030--f1
- f1--030--e2 f2--040--d2 f3--010--c4
- g1--050--b2 g2--040--c3
- */
- void dij_path()
- {
- int weight[N][N] = { {0,100,M,20,1,M,M}
- ,{100,0,20,M,M,M,50}
- ,{M,20,0,5,M,10,40}
- ,{20,M,5,0,M,40,M}
- ,{1,M,M,M,0,30,M}
- ,{M,M,10,40,30,0,M}
- ,{M,50,40,M,M,M,0}
- };
- int path[N][N] = { {0,1,0,2,3,0,0}
- ,{1,0,3,0,0,0,2}
- ,{0,2,0,1,0,4,3}
- ,{1,0,3,0,0,2,0}
- ,{1,0,0,0,0,2,0}
- ,{0,0,3,2,1,0,0}
- ,{0,1,2,0,0,0,0}
- };
- int i, j, src, mid, dest, count, tmp;
- do
- {
- count = 0;/* topo updated, do it again */
- for(src = 0; src < N; src++)
- {
- for(mid = 0; mid < N; mid++)
- {
- if(src == mid) continue;
- for(dest = 0; dest < N; dest++)
- {
- if((src == dest) || (mid == dest)) continue;
- if(weight[mid][dest] == M) continue;
- tmp = weight[src][mid]+weight[mid][dest];
- if((weight[src][dest] == M) || (tmp < weight[src][dest]))
- {
- weight[src][dest] = tmp;
- path[src][dest] = path[src][mid];
- ++count;
- }
- }/* end for(dest */
- }/* end for(mid */
- }/* end for(src */
- }while(count > 0);
- printf("weight[][]:\\n\\t");
- for(i = 0; i < N; i++)
- {
- for(j = 0; j < N; j++)
- {
- printf("%3d ", weight[i][j]);
- }
- printf("\\n\\t");
- }
- printf("path[][]:\\n\\t");
- for(i = 0; i < N; i++)
- {
- for(j = 0; j < N; j++)
- {
- printf("%3d ", path[i][j]);
- }
- printf("\\n\\t");
- }
- }
- ///main.c
- ///
- ///int _tmain(int argc, _TCHAR* argv[])
- ///{
- /// dij_path();
- /// getchar();
- /// return 0;
- ///}
- //该片段来自于http://www.codesnippet.cn/detail/260320149125.html
来源: http://www.codesnippet.cn/detail/260320149125.html