单源最短路径vc源码（贪心算法）

#include <iostream> using namespace std; int n;//包括源在内的顶点数 int **c;//存放顶点到另一个顶点的距离 int *dist;//每个顶点的对应的最短路径长度 int *prev;//从源到i的最短路径上的每个顶点的前一个顶点 void Dijkstra(int n, int v, int dist[], int prev[], int **c) { bool *s = new bool[n +1];//顶点集合，不断的通过贪心选择来扩展这个集合 //初始化 for (int j=1; j<=n; j++) { dist[j] = c[v][j]; s[j] = false; if (dist[j] == -1) prev[j] = 0; else prev[j] = v; } //将第一个顶点放进去 dist[v] = 0; s[v] = true; //贪心法取到下一顶点最小距离的顶点 for (int i=1; i<n; i++) { int temp = 10723; int u = v; for (int p=1; p<=n; p++) { if ((!s[p])&&(dist[p] < temp)&&(dist[p] != -1)) { u =p; temp = dist[p]; } } s[u] = true;//将该结点放入集合s中 for (int j=1; j<=n; j++) { if ((!s[j])&&(c[u][j] != -1)) { int newdist = dist[u] + c[u][j]; if ((newdist < dist[j]) || (dist[j] == -1)) { dist[j] = newdist; prev[j] = u; } } } } delete[] s; } int main() { n = 0; cin >> n; //存储空间开辟 dist = new int[n+1]; prev = new int[n+1]; c = new int *[n+1]; for (int i=1; i<=n; i++) { c[i] = new int[n+1]; } //输入数据 for (int p=1; p<=n; p++) { for (int q=1; q<=n; q++) { cin>>c[p][q]; } } /* //测试数据 c[1][1] = -1;c[1][2] = 10;c[1][3] = -1;c[1][4] = 30;c[1][5]=100; c[2][1] = -1;c[2][2] = -1;c[2][3] = 50;c[2][4] = -1;c[2][5]=-1; c[3][1] = -1;c[3][2] = -1;c[3][3] = -1;c[3][4] = -1;c[3][5]=10; c[4][1] = -1;c[4][2] = -1;c[4][3] = 20;c[4][4] = -1;c[4][5]=60; c[5][1] = -1;c[5][2] = -1;c[5][3] = -1;c[5][4] = -1;c[5][5]=-1; */ //算法调用 Dijkstra(n, 1, dist, prev, c); //结果输出 for (int m=2; m<n; m++) { cout<<dist[m]<<" "; } cout<<dist[n]<<endl; //资源释放 delete[] dist; delete[] prev; for (int k=1; k<=n; k++) { delete[] c[k]; c[k] = NULL; } delete[] c; return 0; }