迪杰斯特拉算法:
问题为:A–>F的最短路径
思路为:
源代码为:
#include <iostream>
#include<stdio.h>
#include<time.h>
#define n 6
int xmin(int p[][n], int i);
int c[n] = { 0 };
int d[2][n] = { 0 };
int main()
{
int a[n][n] = { 0,6,3,1000,1000,1000,6,0,2,5,1000,1000,3,2,0,3,4,1000,1000,5,3,0,2,3,1000,1000,4,2,0,5,1000,1000,1000,3,5,0 };
int i, j, min = 0, s = 0, nn = 0;
for (i = 0; i < n; i++)
d[0][i] = a[0][i];
c[0] = 0;
for (i = 0; i < n;)
{
for (j = i + 1; j < n; j++)
if (d[0][j] > (d[0][c[i]] + a[c[i]][j]))
{
d[0][j] = d[0][c[i]] + a[c[i]][j];
d[1][j] = 1;
}
s = c[i];
c[i += 1] = xmin(d, s);
nn += 1;
if ((c[i] == n - 1) && d[1][j]==0)
{
c[i - 1] = c[i];
nn -= 1;
}
if (c[i] == n - 1)
break;
}
printf("路径为:");
for (i = 0; i <= nn; i++)
{
printf("%d", c[i]);
if (i < nn)
printf("-->");
}
printf("\n最短路径为:");
printf("%d\n", d[0][n-1]);
return 0;
}
int xmin(int p[][n], int i)
{
int j, min = i+1;
for (j = i+1; j < n; j++)
if (p[0][j] < p[0][min])
min = j;
return min;
}