Course Objective:

Students learn important data structures in Computer Science and acquire fundamental algorithm design techniques to get the efficient solutions to several computing problems from various disciplines. Topics include the analysis of algorithm efficiency, hash, heap, graph, tree, sorting and searching, brute force, divide-and-conquer, transform- and-conquer, dynamic programming, and greedy programming.

Example Algorithm:

    /*
    * INSTRUCTION:
    *     This is a C++ starting code for hw6_2.
    *     When you finish the development, download this file.
    *     Note that the current filename is "main.cpp".
    *     But rename it to "main_hw6_2.cpp".
    *     After that, upload the renamed file on Canvas.
    */

    // Finish the head comment with Abstract, Name, and Date.
    /*
    * Title: main_hw6_2.cpp
    * Abstract: Program that implements Floyd's Algorithm to display all-pairs shortest paths
    * Name: Luis Jimenez 
    * Date: 12/13/22
    */

    #include <iostream>
    #include <limits.h> // for INT_MAX
    #include <vector>

    using namespace std;

    // infinity value assume
    const int INF = 99999;

    // Number of vertices in the graph
    int N;

    // Function to implement the Floyd algorithm to find the all-pairs shortest paths
    void floyd(vector<vector<int>>& W)
    {
        // distance matrix to store the lengths of the shortest paths
        vector<vector<int>> D(N, vector<int>(N));

        // initialize the distance matrix with the weight matrix
        // (is not necessary if W can be overwritten)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                D[i][j] = W[i][j];

        // Implement Floyd's algorithm for the all-pairs shortest-paths problem
        for (int k = 0; k < N; k++)
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    // Update the distance matrix
                    D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

        // Print the distance matrix

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (D[i][j] == INF && j != N-1)
                    cout << "-1 ";
                else if (D[i][j] == INF && j == N-1)
                    cout << "-1";
                else if (D[i][j] != INF && j != N-1)
                    cout << D[i][j] << " ";
                else
                    cout << D[i][j];
            }
            cout << endl;
        }
    }

    // main function
    int main()
    {
        cin>>N;

        // weight matrix representing a graph with no negative-length cycle
        vector<vector<int>> W(N, vector<int>(N));

        // Read the weight matrix from the terminal
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cin >> W[i][j];
                if(W[i][j]==-1)
                    W[i][j] = INF;
            }
        }

        floyd(W);

        return 0;
    }