我不想要这个问题的答案，我只需要朝着正确的方向轻推 .
给定无向图G，其具有N（1 <N <= 1000）个顶点和正权重 . 找到从顶点1到顶点N的最短路径，或说明此路径不存在 . 提示：在每个步骤中，在尚未检查的顶点和找到顶点1的路径的顶点中，取一个具有最短路径的顶点，从顶点1到它，但仍然找到 .
首先，我必须定义一个州 . 这就是我说的：
状态是顶点i的解，其中i <= N.较小的状态将是j的解，其中j <i . 要找到状态i，我们需要找到所有较小的状态j（j <i） . 找到了i的最短路径后，我们可以轻松找到下一个状态 - i 1的解决方案 .
我从一个不同的问题中取出了这个，只是替换了变量名和一些单词，因为它听起来适用于这个 .
我必须为解决方案编写程序，但我不知道如何开始 . 这是我的问题：
-
我对国家的定义是否正确？
-
此外，由于这是一个无向图，并且每个顶点都是双向的，权重是否会作为多维数组传入（即
int W[N][2]），其中W[N][0]是一个顶点的权重，W[N][1]是另一个顶点的权重？ -
如何表示最短路径？它是采用的路径数，所采用路径的所有权重之和，还是所采用路径的所有权重的数组？
1 回答
您是否考虑过All-Pairs Shortest Paths算法？例如， Floyd-Warshall algorithm 听起来可能是您的问题的解决方案 .
Floyd-Warshall算法是一种动态编程算法 . Floyd-Warshal算法也支持有向图，因此也是无向的 .
Floyd-Warshall的时间复杂度为Θ（| V | ^ 3），空间复杂度为Θ（| V | ^ 2）
维基百科链接https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
C实现http://www.c-program-example.com/2011/10/c-program-to-implement-warshalls.html
找到路径可以留作练习这个链接有一个例子说明它是如何完成的，但是你需要将它翻译成C.你可以在前辈的矩阵下找到它http://www.programming-algorithms.net/article/45708/Floyd-Warshall-algorithm
这似乎是算法的一个很好的直观表示https://www.cs.usfca.edu/~galles/visualization/Floyd.html
另一种方法是 Bellman Ford algorithm . 这不是所有对最短路径，而是计算从单个点到所有其他顶点的最短路径 .
Bellman-Ford算法是一种动态编程算法 . Bellman-Ford算法也支持加权有向图，因此也是无向的 .
Bellman-Ford的时间复杂度为Θ（| V || E |），空间复杂度为Θ（| V |）
维基百科链接https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
C实现http://www.cs.dartmouth.edu/~cs57/Project/bellman-ford.c
在你的情况下（假设空间复杂性不是问题）在两者之间进行选择主要取决于与边数相比的顶点数 . 通常如果| E |比（| V | ^ 2）大得多，那么你应该选择Warshall-Floyd，否则如果（| V | ^ 2）比| E |大得多 . 你应该和Bellman-Ford一起去 .