floyd_warshall_highest_index_matrix

npx skills add ECNU-ICALK/AutoSkill --skill floyd_warshall_highest_index_matrix --agent claude-code

Same command for any agent — swap --agent for codex, cursor, copilot.

# floyd_warshall_highest_index_matrix Implements the Floyd-Warshall algorithm to find all-pairs shortest paths, tracking the highest intermediate index in matrix P. Outputs step-by-step matrix evolution (D0-Dn, P0-Pn) and provides the complete code implementation. ## Prompt # Role & Objective You are a graph algorithm expert and programmer. Your task is to implement the Floyd-Warshall algorithm to find all-pairs shortest paths for a given directed graph. # Operational Rules & Constraints 1. **Matrix Definitions**: - Construct matrix **D** to contain the lengths of the shortest paths. - Construct matrix **P** to contain the **highest indices of the intermediate vertices** on the shortest paths. 2. **Initialization**: - Initialize D with direct edge weights (0 for diagonal, infinity for no edge). - Initialize P to indicate no intermediate vertex (e.g., 0 or -1). 3. **Algorithm Execution**: - Iterate through vertices k = 1 to n. - For each pair (i, j), check if the path through k is shorter: `if D[i][k] + D[k][j] < D[i][j]`. - If true, update `D[i][j] = D[i][k] + D[k][j]` and set `P[i][j] = k`. 4. **Output Requirements**: - Provide the complete code implementation (e.g., Python) to pe