朴素Dijkstra 邻接矩阵版 c语言

内含完整程序和几组测试数据 /* 输入第一行： 顶点数 边 起点 接下来E行 起点 终点 权重 5 8 0 0 1 1 0 2 5 1 2 1 1 3 8 1 4 3 2 4 1 3 4 6 4 3 1 其中5表示有五个顶点； 8表示有八条边 0表示以0为起点 测试数据：见txt */ #include #include #define INF -1 long long** newMat(long long V); void printMat(long long** mat, long long length); void readMat(long long** mat, long long num); long long* dijkstra(long long** mat, long long length, long long r); int main(int argc, char const* argv[]) { long long V, E, r; long long i, j; scanf("%lld%lld%lld", &V, &E, &r); //初始化数组 long long** weight_mat = newMat(V); readMat(weight_mat, E); // printMat(weight_mat, V); dijkstra(weight_mat, V, r); return 0; } void printMat(long long** mat, long long length) { long long i, j; for (i = 0; i < length; i++) { for (j = 0; j < length; j++) { printf("%lld\t", mat[i][j]); } printf("\n"); } printf("\n"); } long long** newMat(long long V) { long long i, j; long long** mat = (long long**)malloc(sizeof(long long*) * V); for (i = 0; i < V; i++) { mat[i] = (long long*)malloc(sizeof(long long) * V); for (j = 0; j < V; j++) { mat[i][j] = INF; } mat[i][i] = 0; } return mat; } void readMat(long long** mat, long long num) { long long s, t, d; long long i; for (i = 0; i < num; i++) { scanf("%lld%lld%lld", &s, &t, &d); mat[s][t] = d; } } long long* dijkstra(long long** mat, long long length, long long r) { long long* distance = (long long*)malloc(sizeof(long long) * length); char mark[100000]; long long i, j, k, l, min; for (i = 0; i < length; i++) { distance[i] = mat[r][i]; mark[i] = 0; } mark[r] = 1; for (i = 1; i < length; i++) { //找到一个未使用的节点 min = length; for (j = 0; j < length; j++) { if (mark[j] || distance[j] == INF) { continue; } else {