Using Floyd-Warshall algorithm to determine an "odd" matrix

2
votes

Basically the point of using the Floyd-Warshall algorithm is to determine the shortest path between two nodes in a connected graph. What I am attempting to do is instead of simply finding the shortest path, I want the shortest path that is also an even weight.

For instance, this is a simple implementation of the Floyd-Warshall algorithm:

#include <stdio.h>

main()
{
   int dist[10][10],succ[10][10],n,i,j,k;
    int newDist;

    scanf("%d",&n);
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
        {
            dist[i][j]=999;
            succ[i][j]=j;
        }

    while (1)
    {
        scanf("%d %d %d",&i,&j,&k);

        if (i==(-1))
            break;

        dist[i][j]=k;
        distOdd[i][j]=k;
        distEven[i][j]=k;
    }

    printf("    ");

    for (i=0;i<n;i++)
        printf("%3d   ",i);

    printf("\n");

    for (i=0;i<n;i++)
    {
        printf("%3d ",i);

        for (k=0;k<n;k++)
            printf("%3d %d ",dist[i][k],succ[i][k]);

        printf("\n");
    }

    printf("-------------------------------\n");

    /* Floyd-Warshall */
    for (j=0;j<n;j++)
    {
        for (i=0;i<n;i++)
            if (dist[i][j]<999)
                for (k=0;k<n;k++)
                {
                    newDist=dist[i][j]+dist[j][k];
                    if (newDist<dist[i][k])
                    {
                        dist[i][k]=newDist;
                        succ[i][k]=succ[i][j];
                    }
                }

        printf("    ");

        for (i=0;i<n;i++)
            printf("%3d   ",i);
        printf("\n");

        for (i=0;i<n;i++)
        {
            printf("%3d ",i);

            for (k=0;k<n;k++)
                printf("%3d %d ",dist[i][k],succ[i][k]);

            printf("\n");
        }

        printf("-------------------------------\n");
    }

    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            if (dist[i][j]==999)
                printf("No path from %d to %d\n",i,j);
            else
            {
                printf("Distance %d for %d ",dist[i][j],i);
                for (k=succ[i][j];
                    k!=j;
                    k=succ[k][j])
                        printf("%d ",k);

                printf("%d\n",j);
            }
}

Given the following input:

6
0 1 1
1 2 1
2 3 1
3 1 1
1 4 1
4 5 1
-1 -1 -1

I want the following output (ignore the formatting, I simply need a way to find the "odd matrix at each step)

initial odd matrix
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1   1 2 999 3   1 4 999 5 
999 0 999 1 999 2   1 3 999 4 999 5 
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 0
odd matrix
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1   1 2 999 3   1 4 999 5 
999 0 999 1 999 2   1 3 999 4 999 5 
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 1
odd matrix
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1   1 2 999 3   1 4 999 5 
999 0 999 1 999 2   1 3 999 4 999 5 
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0 999 1   2 1 999 3   2 1 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1   2 1 999 3   2 1 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 2
odd matrix
999 0   1 1 999 2   3 1 999 4 999 5 
999 0 999 1   1 2 999 3   1 4 999 5 
999 0 999 1 999 2   1 3 999 4 999 5 
999 0   1 1 999 2   3 1 999 4 999 5 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0 999 1   2 1 999 3   2 1 999 5 
999 0 999 1 999 2   2 2 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1   2 1 999 3   2 1 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 3
odd matrix
999 0   1 1   5 1   3 1   5 1 999 5 
999 0   3 2   1 2   5 2   1 4 999 5 
999 0   5 3   3 3   1 3   3 3 999 5 
999 0   1 1   5 1   3 1   5 1 999 5 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0   4 1   2 1   6 1   2 1 999 5 
999 0   6 2   4 2   2 2   4 2 999 5 
999 0   2 3   6 3   4 3   6 3 999 5 
999 0   4 1   2 1   6 1   2 1 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 4
odd matrix
999 0   1 1   5 1   3 1   5 1   3 1 
999 0   3 2   1 2   5 2   1 4   5 2 
999 0   5 3   3 3   1 3   3 3   7 3 
999 0   1 1   5 1   3 1   5 1   3 1 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0   4 1   2 1   6 1   2 1   6 1 
999 0   6 2   4 2   2 2   4 2   2 4 
999 0   2 3   6 3   4 3   6 3   4 3 
999 0   4 1   2 1   6 1   2 1   6 1 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 5
odd matrix
999 0   1 1   5 1   3 1   5 1   3 1 
999 0   3 2   1 2   5 2   1 4   5 2 
999 0   5 3   3 3   1 3   3 3   7 3 
999 0   1 1   5 1   3 1   5 1   3 1 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0   4 1   2 1   6 1   2 1   6 1 
999 0   6 2   4 2   2 2   4 2   2 4 
999 0   2 3   6 3   4 3   6 3   4 3 
999 0   4 1   2 1   6 1   2 1   6 1 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------

What my code currently does is it gets the most optimal weight which is represented in each of the separate "odd" and "even" matrices.

My lack of understanding is how the "odd" and "even" matrices come up with their non-optimal values when the optimal value is located in the opposite matrix (odd/even). It seems to me that there would have to be some sort of looping or recursion in order to do it, but I'm lost as to how I would accomplish this.

1
calgorithmpath-findingfloyd-warshall
I am not sure if this is going to work, but it's worth a try: split weights into distOdd and distEven matrices, then run three nested loops. On each step perform four tasks: (1) check if two even paths at [i][j] and [j][k] can improve an even path at [i][k], (2) see if two odd paths can improve an even path at [i][k], and (3) see if an odd path at [i][j] and an even one at [j][k] can improve an odd path at [i][k], and (4) see if an even path at [i][j] and an odd one at [j][k] can improve an odd path at [i][k]. - Sergey Kalinichenko
@dasblinkenlight My problem is that the algorithm already finds the most optimal path. For example during Process column 3 the optimal path from 2->1 would have weight '2' but since 2 is an even number, somehow it finds the number '5' which seems to come from looping through node 3 one time and since the algorithm doesn't support recursiveness, I either need to somehow add it or find another way to find it. - Jason M.

1 Answers

2
votes

Not in C but that shouldn't be a problem. I believe F-W needs two modifications to get shortest odd/even paths:

  1. It needs to run twice. This is because if a path loops on itself it may switch evenness. Like in this graph: A --5--> B --2--> (back to A). To get from A to B on an even path, we need to go A-B-A-B. However, if we can't get a path of a certain evenness running it twice, there is no point to run more than twice.

  2. You need to try all the combinations for finding a better path (see the innermost loops that go from 0 to 1). A so-far-even path may become a new best odd path by adding an odd edge, etc.

I think this algorithm should be correct, if you find any mistakes, feel free to yell at me. >D

Edit: added path memorization (parts marked by // ADDED). Of course, this makes the algorithm memory inefficient so should only be used if it is really needed. ATM I can't think of a way to get the standard F-W path reconstruction to work in this case. As a path can be longer than the number of vertices, I am not sure how path reconstruction would work. I have not tested the path memorization extensively so it may be bugged. Probably works ok though.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 5;

            // Generate graph
            Random r = new Random(1);
            // ADDED
            List<int>[,,] path = new List<int>[n, n, 2];
            int[,,] cost = new int[n, n, 2];
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    // ADDED
                    path[i, j, 0] = new List<int>{i};
                    path[i, j, 1] = new List<int>{i};

                    if (i == j)
                    {
                        cost[i, j, 0] = 0;
                        cost[i, j, 1] = -1;
                        continue;
                    }
                    int x = r.Next() % 9 + 1;

                    if (r.Next(100) < 60)
                    {
                        cost[i, j, 0] = -1;
                        cost[i, j, 1] = -1;
                        continue;
                    }

                    cost[i, j, x % 2] = x;
                    cost[i, j, 1 - (x % 2)] = -1;
                }
            }

            // Print edge weights
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (cost[i, j, 0] != -1)
                        Console.Write(cost[i, j, 0] + "\t");
                    else
                        Console.Write(cost[i, j, 1] + "\t");
                }
                Console.WriteLine(" ");
            }
            Console.ReadLine();

            // Find shortest odd and even paths
            for (int s = 0; s < 2; s++)
            {
                for (int k = 0; k < n; k++)
                    for (int i = 0; i < n; i++)
                        for (int j = 0; j < n; j++)
                            for (int u = 0; u <= 1; u++)
                                for (int v = 0; v <= 1; v++)
                                {
                                    if (cost[i, k, u] == -1 || cost[k, j, v] == -1)
                                        continue;
                                    int newCost = cost[i, k, u] + cost[k, j, v];
                                    if (newCost < cost[i, j, newCost % 2] || cost[i, j, newCost % 2] == -1)
                                    {
                                        cost[i, j, newCost % 2] = newCost;
                                        // ADDED
                                        path[i, j, newCost % 2] = path[i, k, u].Concat(path[k, j, v]).ToList();
                                    }
                                }
            }

            // Print results
            Console.WriteLine("\nShortest even paths: ");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    Console.Write(cost[i, j, 0] + "\t");
                Console.WriteLine(" ");
            }

            Console.WriteLine("\nShortest odd paths:");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    Console.Write(cost[i, j, 1] + "\t");
                Console.WriteLine(" ");
            }

            Console.WriteLine();

            // ADDED
            // Example, print shortest odd path between vertices 3 and 1
            // This does not print the final q vertex
            int p = 3;
            int q = 1;
            foreach (int index in path[p, q, 1])
                Console.Write(index);

            Console.ReadLine();
        }
    }
}