数据结构与算法（十四）——图的最短路径问题

//
//  main.c
//  Dijkstra
//
//  Created by 拉维 on 2022/4/29.
//

#include <stdio.h>
#include <stdbool.h>

#pragma mark - 创建一个图

// 无穷值
#define INFINITY 95535

// 图中顶点最大数量
#define Max_Vertexes_count 20

// 图结构
typedef struct Graph {
  int vertexes[Max_Vertexes_count]; // 顶点表
  int edges[Max_Vertexes_count][Max_Vertexes_count]; // 边表
  int countOfVertexes; // 顶点数
  int countOfEdges; // 边数
} Graph;

// 创建图
void createGraph(Graph *graph) {
  // 初始化顶点数、边数
  graph->countOfVertexes = 9;
  graph->countOfEdges = 16;

  // 初始化顶点表
  for (int i = 0; i < graph->countOfVertexes; i++) {
    graph->vertexes[i] = i;
  }

  // 初始化边表
  for (int i = 0; i < graph->countOfVertexes; i++) {
    for (int j = i; j < graph->countOfVertexes; j++) {
      graph->edges[i][j] = i == j ? 0 : INFINITY;
    }
  }

  // 个性化边表信息
  graph->edges[0][1]=1;
  graph->edges[0][2]=5;
  graph->edges[1][2]=3;
  graph->edges[1][3]=7;
  graph->edges[1][4]=5;

  graph->edges[2][4]=1;
  graph->edges[2][5]=7;
  graph->edges[3][4]=2;
  graph->edges[3][6]=3;
  graph->edges[4][5]=3;

  graph->edges[4][6]=6;
  graph->edges[4][7]=9;
  graph->edges[5][7]=5;
  graph->edges[6][7]=2;
  graph->edges[6][8]=7;

  graph->edges[7][8]=4;

  // 无向图需要对称
  for (int i = 0; i < graph->countOfVertexes; i++) {
    for (int j = i+1; j < graph->countOfVertexes; j++) {
      graph->edges[j][i] = graph->edges[i][j];
    }
  }
}

#pragma mark - 最短路径

void shortestPath(Graph graph, int v0, int endVertex) {
  /*
   1，声明三个数组。
   foundStatus是一个数组，元素个数等于图的顶点个数。
   foundStatus[i]表示是否已经求得顶点V0到顶点Vi的最短路径，true是已经求得，false是暂未求得

   *shortestDiscounts是一个int类型的数组，其元素个数等于图的顶点个数。
   *shortestDiscounts[i]表示，顶点V0到顶点Vi的最短路径值是多少

   *previousVertexes是一个数组。
   *previousVertexes[i]表示，顶点i在最短路径上的上一个顶点（前驱顶点）是谁。
   如果顶点i是第一个顶点，则*previousVertexes[i]=-1
   */
  bool foundStatus[graph.countOfVertexes];
  int shortestPathValues[graph.countOfVertexes];
  int previousVertexes[graph.countOfVertexes];

  // 2，初始化
  for (int i = 0; i < graph.countOfVertexes; i++) {
foundStatus[i] = false;
shortestPathValues[i] = graph.edges[v0][i];
previousVertexes[i] = v0;
  }

foundStatus[v0] = true;
shortestPathValues[v0] = 0;
previousVertexes[v0] = -1;

  // 3，遍历各个顶点
for (int i = 1; i < graph.countOfVertexes; i++) {
    // 3.1 找寻shortestPathValues数组中最小的那个路径值min，并确定对应的顶点vertexIndex
int min = INFINITY; // 最小路径值
int vertexIndex = v0; // 最小路径值对应的顶点下标
for (int j  = 0; j < graph.countOfVertexes; j++) {
if (!foundStatus[j] && shortestPathValues[j] < min) {
min = shortestPathValues[j];
vertexIndex = j;
      }
    }

    // 3.2 将顶点vertexIndex标记为已经确定找到了最短路径
foundStatus[vertexIndex] = true;

    // 找到指定两个顶点间的最短路径后，打印该最短路径信息
if (vertexIndex == endVertex) {
int tempIndex = endVertex;
while (tempIndex != v0) {
printf("[%d, %d] = %d\n", previousVertexes[tempIndex], tempIndex, graph.edges[previousVertexes[tempIndex]][tempIndex]);
tempIndex = previousVertexes[tempIndex];
      }
return;
    }

    // 3.3 找寻与顶点vertexIndex连接的其他顶点，看看顶点v0通过顶点vertexIndex抵达这些顶点会不会更短一些
for (int i = 0; i < graph.countOfVertexes; i++) {
if (!foundStatus[i] && (min + graph.edges[vertexIndex][i] < shortestPathValues[i])) {
shortestPathValues[i] = min + graph.edges[vertexIndex][i];
previousVertexes[i] = vertexIndex;
      }
    }
  }
}

int main(int argc, const char * argv[]) {
  // insert code here...
printf("Hello, World!\n");

Graph graph;
createGraph(&graph);
shortestPath(graph, 3, 5);

return 0;
}