Using Floyd-Warshall algorithm to determine an “odd” matrix
https://stackoverflow.com/questions/11900830
-
25-06-2021 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
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.
Решение
Not in C but that shouldn't be a problem. I believe F-W needs two modifications to get shortest odd/even paths:
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.
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();
}
}
}
